[BaekJoon] 5427 불 :: monton

문제

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

풀이

가중치없이 최단 거리를 구하는 것이므로 bfs를 사용

불을 넣을 큐 하나와 상근이의 위치를 넣을 큐 하나씩 해서 큐를 모두 두개 사용한다.

불을 넣은 큐를 일단 pop을 해주고 그 다음 상근이 큐를 pop 해준다

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int W, H,flag,ans;
char arr[1001][1001];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int fmap[1001][1001], smap[1001][1001];
 
void init() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            smap[i][j] = fmap[i][j] = 0;
        }
    }
    ans = flag = 0;
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> W >> H;
        init();
        queue <int>sx, sy, fx, fy;
 
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> arr[i][j];
                if (arr[i][j] == '@') sx.push(i), sy.push(j);
                if (arr[i][j] == '*') fx.push(i), fy.push(j);
            }
        }
 
        while (!sx.empty()) {
            ans++;
            int fcnt = fx.size();
            while (fcnt--) {
                int x = fx.front(), y = fy.front();
                fx.pop(), fy.pop();
 
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                    if (arr[nx][ny] == '*' || arr[nx][ny] == '#' || fmap[nx][ny]) continue;
                    fx.push(nx), fy.push(ny);
                    fmap[nx][ny] = 1;
                }
            }
 
            int scnt = sx.size();
            while (scnt--) {
                int x = sx.front(), y = sy.front();
                sx.pop(), sy.pop();
                if (x == 0 || y == 0 || x == H - 1 || y == W - 1) {
                    flag = 1;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                    if (arr[nx][ny] == '*' || arr[nx][ny] == '#' || fmap[nx][ny]|| smap[nx][ny]) continue;
                    sx.push(nx), sy.push(ny);
                    smap[nx][ny] = 1;
                }
            }
            if (flag) break;
        }
        if (flag) cout << ans << endl;
        else cout << "IMPOSSIBLE" << endl;
    }
}