BOJ 4179 : 불!

풀이요약

BFS

풀이상세

1. 불과 지훈의 이동을 함께 작업하는 경우, 매 반복마다 불을 찾아 진행하기 어려울 수 있다.

2. 따라서 누적합의 개념으로 불이 얼마 후에 각 좌표에 영역을 넓혀 도달하는지 미리 파악해놓고, 구하는 것이 좋다. 따라서 불을 넓히는 BFS() 와 지훈이 이동하는 BFS() 총 2회 진행해야 한다.

3. 불을 넓히는 BFS() 의 경우 초기 불의 좌표와 $dist=1$ 을 집어넣고 매 탐색마다 $dist+1$ 한 값을 저장하면 된다. 불이 도달하지 못하는 지역의 경우에는 $3005$ 를 저장하였다. 이후 지훈의 $dist$ 와 비교하며 불의 $dist$ 보다 지훈의 $dist$ 가 작다면 지훈은 해당 좌표로 움직일 수 있는 것이다.

4. 지훈이 이동하는 BFS() 를 통해 가장 먼저 도착했을 때의 $dist$ 값이 정답이 된다.

조심할 점

1. 만약 어떤 경우의 수로도 도달하지 못하는 경우가 있다면 “IMPOSSIBLE”을 출력하자.
2. 불이 반드시 있다고 문제에서 이야기 한 적 없다. 불이 없는 경우도 고민해보자.
3. 이미 출구에서 지훈이 시작하는 경우가 있다. 이 때의 출력 값은 $1$ 이어야 한다.

배운 점

• BFS 로 도달하면 더 살펴볼 필요도 없이 그게 곧 최단 경로이거늘.

BFS

#include <iostream>
#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;
int N, M, ans = 0;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
vvi v, fire_v, visited;
pi P;
vi dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};

void input() {
    cin >> N >> M;
    v = vvi(N, vi(M, 0));
    visited = vvi(N, vi(M, 0));
    fire_v = vvi(N, vi(M, 0));
    string str;
    queue<pii> fq;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < M; j++) {
            if (str[j] == '.') v[i][j] = 0;
            else if (str[j] == 'J') {
                v[i][j] = 1;
                P = {i, j};
            } else if (str[j] == 'F') {
                v[i][j] = 2;
                fire_v[i][j] = 1;
                fq.push({{i, j}, 1});
            } else v[i][j] = 3;

            if (fire_v[i][j] == 0) fire_v[i][j] = 3005;
        }
    }

    while (!fq.empty()) {
        pii curr = fq.front();
        fq.pop();
        for (int d = 0; d < 4; d++) {
            int nr = curr.f.f + dr[d];
            int nc = curr.f.s + dc[d];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (v[nr][nc] == 3) continue;
            if (fire_v[nr][nc] > curr.s + 1) {
                fire_v[nr][nc] = curr.s + 1;
                fq.push({{nr, nc}, curr.s + 1});
            }
        }
    }
}

int bfs(pi pos) {
    queue<pii> q;
    q.push({pos, 1});
    visited[pos.f][pos.s]++;

    while (!q.empty()) {
        pii curr = q.front();
        q.pop();
        if (curr.f.f == 0 || curr.f.f == N - 1 || curr.f.s == 0 || curr.f.s == M - 1) {
            return curr.s;
        }
        for (int d = 0; d < 4; d++) {
            int nr = curr.f.f + dr[d];
            int nc = curr.f.s + dc[d];
            if (v[nr][nc] >= 2) continue;
            if (visited[nr][nc]) continue;
            if (fire_v[nr][nc] <= curr.s + 1) continue;
            visited[nr][nc]++;
            q.push({{nr, nc}, curr.s + 1});
        }
    }

    return 0;
}

void output() {
    if (!ans) cout << "IMPOSSIBLE";
    else cout << ans;
}

int main() {
    input();
    ans = bfs(P);
    output();
}