[ 백준 ] 5427 / 불

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
5/228
post-thumbnail

# Appreciation

/*
 * Problem :: 5427 / 불
 * 
 * Kind :: Simulation + BFS
 *
 * - 불도 번지고 상근이도 뛴다
 *   + 둘 모두 동서남북 인접한 칸으로 이동할 수 있다
 *     # 둘 모두 BFS 를 돌려주자
 *       -> 순서는 불이 먼저 번지고 상근이가 도망친다
 *          그래야만 문제 설명의 '불이 옮겨진 칸 또는 이제 불이 붙으려는 칸' 으로 이동하는 것을
 *          사전에 방지할 수 있다
 *
 * Point
 * - 상근이가 건물 모서리에 도착할 수 있다면
 *   1초 후, 건물 밖으로 이동하여 무조건 탈출할 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point { int y, x; };
int dy[4] = {-1, 0, 0, +1};
int dx[4] = {0, +1, -1, 0};

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int W, H;
        cin >> W >> H;
        char B[H][W];
        int sy = -1, sx = -1;
        queue<Point> F;
        bool isVisited[H][W];
        memset(isVisited, false, sizeof(isVisited));
        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                cin >> B[i][j];
                if (B[i][j] == '@') {
                    sy = i, sx = j; /* 시작지점 초기화 */
                    B[i][j] = '.';
                    isVisited[i][j] = true; /* 방문 처리 */
                } else if (B[i][j] == '*') {
                    F.push({i, j});
                }
            }
        }

        // Process
        int time = -1; /* 탈출에 걸린 시간 */
        queue<Point> Q;
        Q.push({sy, sx});

        int ans = -1;
        while (not(Q.empty()) && ans == -1) {
            time++;

            /* 불이 번짐 */
            auto sz = F.size();
            while (sz--) {
                auto [cy, cx] = F.front();
                F.pop();

                for (int i=0; i<4; i++) {
                    int ay = cy + dy[i];
                    int ax = cx + dx[i];
                    if (ay >= 0 && ay < H && ax >= 0 && ax < W) {
                        if (B[ay][ax] == '.') {
                            B[ay][ax] = '*';
                            F.push({ay, ax}); /* 새로 번진 불 */
                        }
                    }
                }
            }

            /* 상근이 도망침 */
            sz = Q.size();
            while (sz--) {
                auto [cy, cx] = Q.front();
                Q.pop();

                /* 건물 모서리에 도착하면 */
                if (cy == 0 || cy == H-1 || cx == 0 || cx == W-1) {
                    ans = time+1; /* 탈출 */
                    break;
                }

                for (int i=0; i<4; i++) {
                    int ay = cy + dy[i];
                    int ax = cx + dx[i];
                    if (ay >= 0 && ay < H && ax >= 0 && ax < W) {
                        if (B[ay][ax] == '.' && not(isVisited[ay][ax])) {
                            isVisited[ay][ax] = true;
                            Q.push({ay ,ax});
                        }
                    }
                }
            }
        }

        // Control : Output
        if (ans == -1)
            cout << "IMPOSSIBLE" << endl;
        else
            cout << ans << endl;
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글