[백준 4179번] 불!

문제 링크:https://www.acmicpc.net/problem/4179

4179번: 불!

 

<문제 풀이> BFS 알고리즘

이문제는 여러 개의 시작점을 갖는 불에 대해서 BFS를 먼저 돌려서 불의 도착 시간을 구한 뒤에, BFS를 사용해서 각 위치에 대해서 지훈이가 불 보다 먼저 갈 수 있으면 그 위치에 지훈이의 도착 시간을 갱신하면 됩니다.

 

여러 개의 시작점을 갖는 불을 동시에 BFS로 출발시키는 방법은 처음 시작점을 모두 큐에 넣고 기본적인 BFS을 진행하면 됩니다.

 

지훈이가 불 보다 먼저 갈 수 있는지 확인하는 방법은 현재 위치에서 (지훈이의 도착 시간 + 1) < (불의 도착 시간)이면 지훈이가 불 보다 먼저 갈 수 있습니다. (2차원 visited 배열 2개가 필요)

 

그리고 next 좌표가 배열의 범위를 넘어가면 지훈이가 탈출에 성공한 거니깐 지훈이의 도착 시간을 return 하면 됩니다.

만약 큐의 원소가 모두 비게 되면 지훈이의 위치가 한 번도 배열의 범위를 못 넘은 거니깐 지훈이는 탈출에 실패한 게 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <utility>
#include <queue>
using namespace std;
 
#define X first
#define Y second
 
char board[1000][1000];
int F_dist[1000][1000];
int J_dist[1000][1000];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int r, c;
 
void F_bfs() {
    queue<pair<int, int> > Q;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j] == 'F') {
                Q.push({ i, j });
                F_dist[i][j] = 1;
            }
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx>=r || ny >= c) continue;
            if (board[nx][ny] == '#' || F_dist[nx][ny])continue;
            Q.push({ nx,ny });
            F_dist[nx][ny] = F_dist[cur.X][cur.Y] + 1;
        }
    }
}
 
int J_bfs() {
    F_bfs();
    queue<pair<int, int> > Q;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j] == 'J') {
                Q.push({ i, j });
                J_dist[i][j] = 1;
            }
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) {//범위를 넘어가면 탈출 성공
                return J_dist[cur.X][cur.Y]; 
            }
            if (board[nx][ny] == '#' || J_dist[nx][ny])continue;
            if (J_dist[cur.X][cur.Y] + 1 >= F_dist[nx][ny] && F_dist[nx][ny]) continue; //불이 더 빨리 도착하면 무시
            Q.push({ nx,ny });
            J_dist[nx][ny] = J_dist[cur.X][cur.Y] + 1;
        }
    }
    return -1;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
    int res = J_bfs();
    if (res != -1) cout << res;
    else cout << "IMPOSSIBLE";
 
 
    return 0;
}