BOJ 4179 불! c++

백준 4179 불 문제 c++

 

#include <bits/stdc++.h>
using namespace std;

//pair<int, int>에 접근하기 위해 define.
# define X first
# define Y second

int n, m;
// 맵을 저장할 2차원 배열.
string board[1002];
// 움직이는 데 걸린 시간을 저장할 2차원 배열.
// J와 F(불)을 위한 두 개의 dist배열 선언.
int distJ[1002][1002];
int distF[1002][1002];
//dx, dy는 상, 하, 좌, 우를 위해 사용할 배열.
//아래에서 자세히 확인.
int dx[] = {0, 1, 0 , -1};
int dy[] = {1, 0, -1, 0};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    
    // BFS를 위한 Queue for J, F
    queue<pair<int, int>> QJ;
    queue<pair<int, int>> QF; 
    // 아래에서 맵 입력.
    for (int i = 0; i < n; i++)
        cin >> board[i];
    // dist배열을 모두 -1로 채움.
    for (int i = 0; i < n; i++){
        fill(distJ[i], distJ[i] + m, -1);
        fill(distF[i], distF[i] + m, -1);
    }
    // 'J'의 위치와 'F'의 위치를 queue에 담음.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'J'){
                QJ.push({i, j});
                distJ[i][j] = 0;
            }
            if (board[i][j] == 'F'){
                QF.push({i, j});
                distF[i][j] = 0;
            }
        }
    }
    // 먼저 불이 전체로 퍼지는 데에 걸리는 시간을 dist[]에 저장.
    while (!QF.empty()) {
        auto cur = QF.front();
        QF.pop();
        for (int dir = 0; dir < 4; dir++) {
            // nx, ny는 시작위치로부터의 상, 하, 좌, 우임.
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            // nx, ny가 범위를 벗어나면 continue
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            // 벽을 만나거나 dist[] 에서 이미 방문한 적이 있으면 continue
            if (board[nx][ny] == '#' || distF[nx][ny] >= 0)
                continue;
            // dist[] 에서 F가 위치한 곳으로부터 1씩 퍼져나감.
            distF[nx][ny] = distF[cur.X][cur.Y] + 1;
            // Queue에 넣어 값이 증가된 지점부터 다시 시작.
            QF.push({nx, ny});
        }
    }
    while (!QJ.empty()) {
        auto cur = QJ.front();
        QJ.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 >= n || ny >= m) {
                cout << distJ[cur.X][cur.Y] + 1;
                return 0;
            }
            // 방문한적이 있거나 벽을 만나면 continue
            if (board[nx][ny] == '#' || distJ[nx][ny] >= 0)
                continue;
            // 불보다 늦게 도착한 경우 continue;
            if (distF[nx][ny] != -1 && distF[nx][ny] <= distJ[cur.X][cur.Y]+1)
                continue;
            distJ[nx][ny] = distJ[cur.X][cur.Y] + 1;
            QJ.push({nx, ny});
        }
    }
    // 여기까지 빠져나와버린다면 불보다 늦게 탈출한 것임.
    cout << "IMPOSSIBLE";   
}