BOJ 4179 불!

사용한 알고리즘

알고리즘 설명

단순한 BFS 문제이다
여기서 불이 붙은 곳은 사람이 갈 수 없다
불과 사람은 상하좌우로 움직일 수 있다
알고리즘 순서는 다음과 같다
1. 현 시간에 있는 모든 불을 사방으로 퍼트린다
1. 현 시간에 사람이 갈 수 있는 위치를 사방으로 퍼트린다
1. 이를 계속 반복하다 밖으로 나가면 그 시간을 출력
1. 여기서 사람이 갈 수 있는 곳이 없다면 IMPOSSIBLE 이다.

풀이

// baekjoon 4179 yechan
#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
const int MAX_N=1001;
const int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0} };

int N, M, sx, sy;
bool visited[MAX_N][MAX_N];
char tmp[MAX_N];
vector<P> fire;

int BFS() {
    queue<P> qFire;
    for (int i=0; i<fire.size(); i++)
        qFire.push(fire[i]);

    queue<P> qPos;
    qPos.push(P(sx, sy));

    int t = 1;
    while (!qPos.empty()) {
        // propgate fire
        int qFireSize = qFire.size();
        for (int i=0; i<qFireSize; i++) {
            P curr_P = qFire.front();
            qFire.pop();
            int curr_x = curr_P.first;
            int curr_y = curr_P.second;
            for (int d=0; d<4; d++) {
                int nx = curr_x + dir[d][0];
                int ny = curr_y + dir[d][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (visited[nx][ny]) continue;
                visited[nx][ny] = true;
                qFire.push(P(nx,ny));
            }
        }

        // propgate me
        int qPosSize = qPos.size();
        for (int i=0; i<qPosSize; i++) {
            P curr_P = qPos.front();
            qPos.pop();
            int curr_x = curr_P.first;
            int curr_y = curr_P.second;
            for (int d=0; d<4; d++) {
                int nx = curr_x + dir[d][0];
                int ny = curr_y + dir[d][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) return t;
                if (visited[nx][ny]) continue;
                visited[nx][ny] = true;
                qPos.push(P(nx,ny));
            }
        }
        t++;
    }
    return -1;
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i=0; i<N; i++) {
        scanf("%s", tmp);
        for (int j=0; j<M; j++) {
            char c = tmp[j];
            if (c == '#') visited[i][j] = true;
            else if (c == 'F') visited[i][j] = true, fire.push_back(P(i,j));
            else if (c == 'J') visited[i][j] = true, sx = i, sy = j;
        }
    }
    int ret = BFS();
    if (ret == -1) puts("IMPOSSIBLE");
    else printf("%d\n", ret);
    return 0;
}