[백준] 4179번 불!

문제: 4179번: 불!

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 main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int r, c; // r: 미로 행의 개수, c: 열의 개수
    cin >> r >> c;

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

    vector<vector<char>> board(r);
    vector<vector<bool>> fvisit(r);
    vector<vector<bool>> jvisit(r);
    vector<vector<int>> dist(r);

    queue<pair<int, int>> jNexts; // 지훈이가 다음에 가는 곳
    queue<pair<int, int>> fNexts; // 불이 다음에 가는 곳
    for (int i = 0; i < r; i++) {
        board[i] = vector<char>(c);
        fvisit[i] = vector<bool>(c);
        jvisit[i] = vector<bool>(c);
        dist[i] = vector<int>(c);

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

            if (board[i][j] == 'J') {
                dist[i][j] = 1;
                jvisit[i][j] = true;
                jNexts.push(make_pair(i, j));
            }
            else if (board[i][j] == 'F') {
                fvisit[i][j] = true; // 방문 표시
                fNexts.push(make_pair(i, j));
            }
        }
    }

    bool flag = false;
    while (!jNexts.empty()) {
        // 불 먼저 이동시키기
        int fSize = fNexts.size();
        while (fSize-- > 0) {
            pair<int, int> fTmp = fNexts.front();
            fNexts.pop();

            for (int i = 0; i < 4; i++) {
                int fNx = fTmp.first + dx[i];
                int fNy = fTmp.second + dy[i];

                if (fNx < 0 || fNx >= r || fNy < 0 || fNy >= c) continue;
                if (fvisit[fNx][fNy] || board[fNx][fNy] == '#') continue;

                fvisit[fNx][fNy] = true;
                board[fNx][fNy] = 'F';
                fNexts.push(make_pair(fNx, fNy));
            }
        }
        
        // 지훈이 이동시키기
        int jSize = jNexts.size();
        while (jSize-- > 0) {
            pair<int, int> jTmp = jNexts.front();
            jNexts.pop();

            for (int i = 0; i < 4; i++) {
                int jNx = jTmp.first + dx[i];
                int jNy = jTmp.second + dy[i];

                if (jNx < 0 || jNx >= r || jNy < 0 || jNy >= c) {
                    flag = true;
                    cout << dist[jTmp.first][jTmp.second];
                    return 0;
                }

                if (jvisit[jNx][jNy] || board[jNx][jNy] == 'F' || board[jNx][jNy] == '#') continue;

                jvisit[jNx][jNy] = true;
                board[jNx][jNy] = 'J';
                jNexts.push(make_pair(jNx, jNy));
                dist[jNx][jNy] = dist[jTmp.first][jTmp.second] + 1; // 거리 갱신
            }
        }
    }
    if (!flag) 
        cout << "IMPOSSIBLE";
   
    return 0;
}

 

3번 제출하고 나서야 비로소 만점을 받았다... 

 

일단 이 문제의 핵심은 불과 지훈이 각각에 대해 BFS 를 돌려야 한다는 것.. 맵 상에 존재하는 모든 불에대해 다 BFS 돌려주고 그 다음에 지훈이 BFS 돌려주면 된다.

 

내가 2번 째 제출 때 틀린 이유는 지훈이 BFS 돌릴 때 각 단계에서 큐에 존재하던 모든 요소에 대해 돌려야 하는데 단계를 신경쓰지 않고 그냥 하나씩 빼서 돌려가지고 제대로 안 됐던 거였다.. -_-;;

 

이 문제는 솔직히 예외처리도 어려웠다. 반례 정리해놓은 글이 있길래 그걸로 코드 잘못된 거 찾아가면서 겨우겨우 풀었다.

 

 

 

참고자료:

[c++] 백준 불!(4179), BFS, 반례모음

[c++] 백준 불!(4179), BFS, 반례모음