greentea31's Note

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

풀이 과정

벽과 지나갈 수 있는 공간, 불과 지훈이의 위치가 주어지고 불은 상하좌우로 하루마다 한칸씩 번지며, 지훈이는 하루에 한칸씩 이동이 가능할 때, 지훈이가 미로에서 탈출할 수 있는지, 탈출이 가능하다면 걸리는 최소 날짜는 몇 일인지 구하는 문제이다.

flood fill bfs 문제이다. 지훈이를 불과 벽을 피해 bfs로 이동시키면서 미로의 밖에 도착이 가능한지, 가능하다면 도착하기까지의 날짜가 얼마나 걸리는지를 구해주면 된다.

풀고나서 다른 사람의 코드를 봤더니 불에 대한 BFS를 먼저 돌리고 각 칸에서 불이 번지는 시간을 먼저 계산후 지훈이의 BFS를 구하는 방법으로 푼 코드가 많았다. 그런데 사실 BFS를 2번 돌릴 필요가 없다. BFS의 시작 시점에 큐에 지훈이의 시작 위치를 넣은 후 불의 위치를 넣어서 지훈이의 진행과정이 불의 진행과정보다 먼저 이루어지게 한 후 BFS를 한번만 돌리면 된다.

# . F

# J #

# # #

같은 경우에 IMPOSSIBLE이 나와야 올바르게 짠 코드이다. 지훈이를 먼저 진행시키는 만큼 지훈이가 모서리에 도착하자마자 탈출 성공 처리를 해버리면 탈출이 가능한 잘못된 답이 나오게 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

char board[1001][1001];
int day[1001][1001];
int R, C;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int 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(make_pair(i, j));
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'F') Q.push(make_pair(i, j));
        }
    }

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (board[cur.first][cur.second] == 'J') {
            if (cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1) {
                return day[cur.first][cur.second];
            }
        }

        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < R && 0 <= nx && nx < C) {
                if (board[cur.first][cur.second] == 'J') {
                    if (board[ny][nx] != '.') continue;
                    board[ny][nx] = 'J';
                    day[ny][nx] = day[cur.first][cur.second] + 1;
                    Q.push(make_pair(ny, nx));
                } else if (board[cur.first][cur.second] == 'F') {
                    if (board[ny][nx] == 'F' || board[ny][nx] == '#') continue;
                    board[ny][nx] = 'F';
                    Q.push(make_pair(ny, nx));
                }
            }
        }
    }

    return -1;
}

int main() {
    ios_base::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 answer = bfs();
    if (answer == -1) cout << "IMPOSSIBLE";
    else cout << answer+1;

    return 0;
}