[백준] 5427 불

문제: 5427번: 불

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t-- > 0) {
        int w, h; // 너비, 높이
        cin >> w >> h;

        vector<vector<char>> board(h);
        vector<vector<int>> FVisit(h); // 불 방문
        vector<vector<int>> SVisit(h); // 상근 방문
        vector<vector<int>> dist(h);

        queue<pair<int, int>> FNexts;
        queue<pair<int, int>> SNexts;

        for (int i = 0; i < h; i++) {
            board[i] = vector<char>(w);
            FVisit[i] = vector<int>(w);
            SVisit[i] = vector<int>(w);
            dist[i] = vector<int>(w);

            for (int j = 0; j < w; j++) {
                cin >> board[i][j];

                if (board[i][j] == '*') {
                    FNexts.push(make_pair(i, j));
                    FVisit[i][j] = 1; // 방문 표시
                }
                else if (board[i][j] == '@') {
                    SNexts.push(make_pair(i, j));
                    SVisit[i][j] = 1; // 방문 표시
                    dist[i][j] = 1;
                }
            }
        }

        bool flag = false; // 탈출 여부
        while (!SNexts.empty()) {
            int FSize = FNexts.size();
            while (FSize-- > 0) {
                pair<int, int> cur = FNexts.front();
                FNexts.pop();

                for (int i = 0; i < 4; i++) {
                    int nx = cur.first + dx[i];
                    int ny = cur.second + dy[i];

                    if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                    if (FVisit[nx][ny] == 1 || board[nx][ny] == '#') continue;

                    board[nx][ny] = '*'; // 불!
                    FNexts.push(make_pair(nx, ny));
                    FVisit[nx][ny] = 1; // 방문 표시!
                }
            }

            int SSize = SNexts.size();
            while (SSize-- > 0) {
                pair<int, int> cur = SNexts.front();
                SNexts.pop();

                for (int i = 0; i < 4; i++) {
                    int nx = cur.first + dx[i];
                    int ny = cur.second + dy[i];

                    if (nx < 0 || nx >= h || ny < 0 || ny >= w) {     
                        flag = true;
                        break;
                    }
                    if (SVisit[nx][ny] == 1 || board[nx][ny] == '*' || board[nx][ny] == '#') continue;

                    board[nx][ny] = '@'; // 상근!
                    SNexts.push(make_pair(nx, ny));
                    SVisit[nx][ny] = 1; // 방문 표시!
                    dist[nx][ny] = dist[cur.first][cur.second] + 1;
                }

                if (flag) {
                    cout << dist[cur.first][cur.second] << "\n";
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
        if (!flag)
            cout << "IMPOSSIBLE\n";
    }

   
    return 0;
}

 

탈출 조건을 만족하면 반복문을 빠져나와야 하는데 이거 하느라 마지막에 flag 를 3번이나 확인해야 해서 개인적으로 코드가 맘에 안 든다. -_-;;

 

이것만 빼면 이전에 풀었던 문제인 4179번 불! 문제랑 다른 점을 못 찾겠다. 그래도 풀어서 기분 좋다 ^~^ 처음 풀었을 땐 예외 처리가 좀 어려웠는데 지금은 아무렇지도 않다 ^*^