[5427] 불

문제: https://www.acmicpc.net/problem/5427

테스트케이스와 현재 빌딩의 너비와 높이, 빌딩 정보가 주어졌을 때

상근이가 불이 번지는 속도보다 출구에 먼저 도달할 수 있냐고 묻는 문제이다.

많은 해결 방안이 있겠지만 나는 출구를 기준으로 BFS를 이용해 최단경로를 구하는 방법으로 풀었다.

먼저 모든 출구(가장자리의 . )들을 큐에 넣어놓고

각각 출구마다 BFS를 수행한다. BFS 수행 중 가장 먼저 만나는 특이점, 즉 벽(#)과 길(.)을 제외하고

불(*)과 상근이(@)중 어떤게 더 가까운지만 확인해서 상근이가 불보다 가까운 출구가 있다면 그곳으로 나갈 수 있다는 뜻이므로

출구부터 상근이까지의 길이를 계산해 반환하고 모든 출구에대해 수행한 후 최솟 값을 찾는 방법으로 풀었다.

물론 다른 방법도 있다.

불들을 먼저 갈수있는 모든 길을 BFS로 거리 값을 미리 계산해 놓고(중복된 지점은 최솟 값으로) 

상근이를 출발시켜 불보다 먼저 가는 길로 출구에 도달할 수 있는지를 확인하는 방법으로도 풀 수 있을 것 같다.

이렇게 푸는게 시간상 더 효율적이겠지만 처음 떠올랐던 출구 방법이 더 쉽게 코드를 작성할 수 있을 것 같아서 처음 방법으로 했다.

다만 처음방법은 상근이가 처음부터 출구에 있을 경우를 예외처리 해주어야한다.

또한 주의할 점이 있는데 상근이와 불이 같은 거리에있는 경우 불보다 상근이가 먼저 큐에 들어와

상근이의 거리가 더 짧다고 생각해 BFS를 종료 할 수있으므로 이런 경우를 대비해 BFS 수행 중 상근이를 발견해도 바로 종료하는게 아니라

현재 출구로부터 같은 거리에 있는 정점들은 모두 수행해 준 후 그때까지 불이 없을 때 종료시켜 줘야한다.

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int arr[1010][1010];
bool visit[1010][1010];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int bfs(int x, int y, int n, int m) {
    queue<pair<int, int> > qu;
    qu.push({ x, y });
    visit[x][y] = 1;
    int cnt = 0;
    bool flag = 0;
    while (int s = (int)qu.size()) {
        while (s--) {
            int cx = qu.front().first;
            int cy = qu.front().second;
            qu.pop();
            if (arr[cx][cy] == 3) return 0;
            if (arr[cx][cy] == 2) {
                flag = 1;
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + cx;
                int ny = dy[i] + cy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && arr[nx][ny] != 1 && !visit[nx][ny]) {
                    visit[nx][ny] = 1;
                    qu.push({ nx, ny });
                }
            }
        }
        if (flag) {
            return cnt;
        }
        cnt++;
    }
    return 0;
}
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--){
        queue<pair<int, int> > exitPos;
        memset(arr, 0, sizeof(arr));
        int n, m;
        bool flag = 0;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char a;
                scanf(" %1c", &a);
                if (a == '#') arr[i][j] = 1;
                else if (a == '@') {
                    arr[i][j] = 2;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        flag = 1;
                    }
                }
                else if (a == '*') arr[i][j] = 3;
                else {
                    arr[i][j] = 4;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        exitPos.push({ i, j });
                    }
                }
            }
        }
 
        if (flag) {
            puts("1");
            continue;
        }
 
        int size = (int)exitPos.size();
        int mini = 987654321, res = 0;
        for (int i = 0; i < size; i++) {
            memset(visit, false, sizeof(visit));
            int x = exitPos.front().first;
            int y = exitPos.front().second;
            exitPos.pop();
            res = bfs(x, y, n, m);
            if (res > 0) {
                mini = min(mini, res+1);
            }
        }
 
        if (mini != 987654321) printf("%d\n", mini);
        else puts("IMPOSSIBLE");
    }
    return 0;
}