#백준 4179번 : 불! #bfs

백준 문제

4179번: 불!

백준 문제 상세

풀이 : bfs를 두개 돌린다고 생각하면 된다.

두개를 동시에 돌려야한다고 생각하지 말고, 영향을 끼치는 방향성을 고려해 보면 된다.

불->지훈 = 죽음 이기 때문에 지훈이 불의 이동에만 영향을 받는 입장.

불은 지훈의 이동을 신경쓰지 않아도 된다.

=> 불의 bfs를 먼저 돌리자!

 

#define X first
#define Y second

//각 위치를 도달하는 데에 걸리는 시간
int J_time[1002][1002];
int F_time[1002][1002];
//각 위치를 방문했는지 여부
bool Jvis[1002][1002];
bool Fvis[1002][1002];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //행, 열 크기 입력받기
    int height, width;
    cin >> height >> width;
    
    string str[1002];
    queue<pair<int, int>> JQ; //지훈 큐
    queue<pair<int, int>> FQ; //불 큐

    for (int i = 0;i < height;i++) {
        cin >> str[i];
        fill(Jvis[i],Jvis[i]+width,0);
        fill(Fvis[i],Fvis[i]+width,0);
        fill(J_time[i], J_time[i] + width, -1);
        fill(F_time[i], F_time[i] + width, -1);
        for (int j = 0;j < width;j++) {
            if (str[i][j] == 'J') { //지훈 찾았을때
                JQ.push({ i,j });
                Jvis[i][j] = 1;
                J_time[i][j] = 0;
            }
            if (str[i][j] == 'F') { //불 찾았을때
                FQ.push({ i,j });
                Fvis[i][j] = 1;
                F_time[i][j] = 0;
            }
        }
    }

    while (!FQ.empty()) {   //불 위치부터 구하기 => 불이 각 위치에 도달하는 시간 대입
        pair<int, int> cur = FQ.front();
        FQ.pop();
        for (int dir = 0;dir < 4;dir++) { //불 한칸씩 퍼져나감
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= height || ny < 0 || ny >= width) continue;
            if (Fvis[nx][ny] || str[nx][ny] == '#') continue; //이미 방문했거나 벽이면 불이 못퍼짐
            FQ.push({ nx,ny });
            Fvis[nx][ny] = 1;
            F_time[nx][ny] = F_time[cur.X][cur.Y]+1; //한칸씩 넓어질때마다 걸리는 시간은 1씩 증가
        }

    }
    
    while (!JQ.empty()) { //지훈 이동 구하기
        pair<int, int> curJ = JQ.front();
        JQ.pop();
        for (int dir = 0;dir < 4;dir++) { // 지훈이 한칸 도망감
            int nx = curJ.X + dx[dir];
            int ny = curJ.Y + dy[dir];
            if (nx < 0 || nx >= height || ny < 0 || ny >= width) { //주어진 배열의 크기를 벗어날 시 탈출 성공!
                cout << J_time[curJ.X][curJ.Y] + 1;
                return 0;
            }
            if (Jvis[nx][ny] || str[nx][ny] == '#') continue;
            if(Fvis[nx][ny]&&J_time[curJ.X][curJ.Y] + 1 >= F_time[nx][ny]) continue;  //여기 첫번째 조건 때문에 고생함. 
            JQ.push({ nx,ny });
            Jvis[nx][ny] = 1;
            J_time[nx][ny] = J_time[curJ.X][curJ.Y] + 1;

        }
    
    }
    cout << "IMPOSSIBLE";
}

나는 지훈의 bfs의 세번째 if문에서 고생했다. (70번째 줄)

 

Fvis[nx][ny]를 안넣고 코드를 돌렸는데, 내가 예제를 넣어서 돌리면 다 맞게 나오는데

백준에서는 죽어도 틀렸다고 해서 하나하나 다 뜯어봤다.

 

결론은 내가 불이랑 지훈이랑 벽으로 막혀있을 경우를 간과해서 그랬었다.

지훈이와 불이 벽으로 막혀있어서 서로 마주칠 일이 없으면

불이 방문하지 않은 곳도 지훈이는 갈 수 있어야 한다.