[백준] 4179번: 불! (C++)

4179번: 불!

---

문제)

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

 

 

입력 :

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

 

출력 :

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int r, c, ans = 0;
int sx, sy;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
 
// 미로, 사람, 불의 이동을 저장할 배열 생성
char vec[1004][1004];
int person_visited[1004][1004];
int fire_visited[1004][1004];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> r >> c;
 
    // 불이 이동하는 경로를 저장해야 하는데,
    // 불이 여러 개이므로 큰 수로 채워준다.
    fill(&fire_visited[0][0], &fire_visited[0][0] + 1004 * 1004, 987654321);
    queue<pair<int, int>> q;
 
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> vec[i][j];
 
            // 불 먼저 이동시키기 위해 queue에 위치를 저장해놓는다.
            if (vec[i][j] == 'F')
            {
                fire_visited[i][j] = 1;
                q.push(make_pair(i, j));
            }
            // 이후에 지훈이의 위치를 사용하기 위해 미리 저장
            else if (vec[i][j] == 'J')
            {
                sx = i;
                sy = j;
            }
        }
    }
 
    // 불의 이동 먼저
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            // 미로의 범위 내에서 이동
            if (0 > nx || nx >= r || 0 > ny || ny >= c) continue;
            // BFS이므로 가까운 곳부터 번진다. (queue에 불의 첫 위치가 먼저 들어가 있음)
            if (fire_visited[nx][ny] != 987654321 || vec[nx][ny] == '#') continue;
            fire_visited[nx][ny] = fire_visited[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }
 
    // 지훈이가 이동하는 bfs이다.
    person_visited[sx][sy] = 1;
    q.push(make_pair(sx, sy));
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        // 미로의 모서리에 도착한다면 탈출할 수 있다.
        if (0 == x || x == r - 1 || 0 == y || y == c - 1)
        {
            ans = person_visited[x][y];
            break;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (0 > nx || nx >= r || 0 > ny || ny >= c) continue;
            if (person_visited[nx][ny] || vec[nx][ny] == '#') continue;
            // 지훈이는 불보다 먼저 이동해야 살 수 있다.
            if (fire_visited[nx][ny] <= person_visited[x][y] + 1) continue;
            person_visited[nx][ny] = person_visited[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }
 
    if (ans != 0)
    {
        cout << ans;
    }
    else
    {
        cout << "IMPOSSIBLE";
    }
 
    return 0;
}

 

 

---

출처 : https://www.acmicpc.net/problem/4179 

4179번: 불!