<백준> 4179 불! / C++ 풀이

중점:

1. 불에 대한 bfs와 사람에 대한 bfs를 두번 시행

2. 불에 대한 bfs를 먼저 시행

3. 사람에 대한 bfs를 시행 하는 경우 vis1에 대한 조건을 확인한다 (불이 먼저 옮겼는지에 대한 파악을 한다)

---

정답 코드:

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

string borad[1005];
int vis1[1005][1005];
int vis2[1005][1005];
int r, c;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> r >> c;

    for (int i = 0; i < r; i++){
        cin >> borad[i];
    }

    for (int i = 0; i < r; i++){
        fill(vis1[i], vis1[i] + c, -1);
        fill(vis2[i], vis2[i] + c, -1);
    }

    queue<pair<int, int> > Q1;
    queue<pair<int, int> > Q2;

    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            if(borad[i][j] == 'F'){
                Q1.push({i, j});
                vis1[i][j] = 0;
            }

            if(borad[i][j] == 'J'){
                Q2.push({i, j});
                vis2[i][j] = 0;
            }
        }
    }

    while (!Q1.empty())
    {
        pair<int, int> cur = Q1.front();
        Q1.pop();

        for (int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if(borad[nx][ny] == '#' || vis1[nx][ny] >= 0) continue;

            vis1[nx][ny] = vis1[cur.X][cur.Y] + 1;
            Q1.push({nx, ny});
        }
    }
    
    while (!Q2.empty())
    {
        pair<int, int> cur = Q2.front();
        Q2.pop();

        for (int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if(nx < 0 || nx >= r || ny < 0 || ny >= c){
                cout << vis2[cur.X][cur.Y] + 1;
                return 0;
            }
            if(borad[nx][ny] == '#' || vis2[nx][ny] >= 0) continue;
            if(vis1[nx][ny] != -1 && vis1[nx][ny] <= vis2[cur.X][cur.Y] + 1) continue; //불이 안나는 경우 존재.

            vis2[nx][ny] = vis2[cur.X][cur.Y] + 1;
            Q2.push({nx, ny});
        }
    }

    cout << "IMPOSSIBLE";
}