백준 : 5427번 불(c++) BFS문제

백준 링크

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

5427번: 불

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	34601	9111	6026	24.285%

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

코드 풀이

이번 문제는 BFS 방식으로 풀이했습니다.

정답 비율이 낮은만큼 단순하지는 않았다.

기본적으로 불과 사람과의 순서도 따져야 하고 구조 잡기도 생각보다 까다로운 문제였다.

필자의 경우 예제를 담기위한 BoardFill함수와 BFS를 탐색하는 함수 두 개로 나누어서 풀이를 진행하였다.

1. TestCase만큼 돌려야 하기 때문에 TestCast만큼의 반복문 설정

2. for문 내부에 탐색에 필요한 변수와 함수 지정 (로테이션 한 번들면 다 초기화됨)

3. BoardFill함수는 Board벡터에 예제 정보를 넣는 함수

4. BFS함수는 탐색을 진행하는 함수

4.a 먼저 큐에 불, 사람을 넣어줘야 하는데 이때 순서가 중요한데 설명을 잘 확인해 보면 순서를 알 수 있다.

문제 설명에 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다라고 나와있는데 이는 불이 먼저 움직이고 사람이 나중에 움직여야 한다는 것을 알 수 있다.

결국 queue에 존재하는 불 위치를 먼저 넣고 그다음 사람의 위치를 넣는다.

4.b  큐가 빌 때까지 반복을 돌리는데 이때도 큐에서 꺼낸 값이 불인 지 사람인지 판단하여 구현해야 한다.

만약에 사람이고 인덱스 범위를 벗어났다면 탈출을 한 것이기 때문에 return true를 진행하였고 그게 아니고 예외처리를 통과했다면 다시 큐에 다음 위치값을 넣어주었다.

4.c 큐의 front가 불이라면 동일하게 예외처리를 해주는데 단 주의해야 할 점이 불은 인덱스 범위를 벗어날 수 없는 것을 주의해야 한다. 이거 이외에는 동일

 

필자의 경우 한 번에 통과해서 나름 행복했고 ㅋ,ㅋ 생각보다 재밌는 문제였던 거 같다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>


using namespace std;

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

pair<int, int> PlayerPos;
vector<pair<int, int>> vecFirePos;

void BoardFill(vector<string>& _Board, int X, int Y)
{
    vecFirePos.clear();
    for (int j = 0; j < Y; ++j)
    {
        string s;
        s.resize(X);
        for (int k = 0; k < X; ++k)
        {
            cin >> s[k];

            if (s[k] == '@')
            {
                PlayerPos = { j, k };
            }
            else if (s[k] == '*')
            {
                vecFirePos.push_back({ j, k });
            }
        }
        _Board.push_back(s);
    }
}

bool BFS(vector<string>& _Board, vector<vector<bool>>& _PlayerVisit, vector<vector<bool>>& _FireVisit,
    vector<vector<int>>& _Dist, int X, int Y, int& _Count)
{
    queue<pair<int, int>> qPair;
    queue<bool> qJudgment;      // 불인지 사람인지 판단하기 위한 큐

    int FireSize = static_cast<int>(vecFirePos.size());

    // 불 우선 퍼지기 때문에 불을 큐에 먼저 넣는다.
    for (int i = 0; i < FireSize; ++i)
    {
        qPair.push({ vecFirePos[i].first, vecFirePos[i].second });
        qJudgment.push(false);
        _FireVisit[vecFirePos[i].first][vecFirePos[i].second] = true;
    }
    // 플레이어를 넣는다.
    qPair.push({ PlayerPos.first, PlayerPos.second });
    _Dist[PlayerPos.first][PlayerPos.second] = 0;
    qJudgment.push(true);
    _PlayerVisit[PlayerPos.first][PlayerPos.second] = true;

    while (!qPair.empty())
    {
        pair<int, int> Cur = qPair.front();
        bool Type = qJudgment.front();
        qPair.pop();
        qJudgment.pop();

        for (int Dir = 0; Dir < 4; ++Dir)
        {
            int NextX = Cur.second + dx[Dir];
            int NextY = Cur.first + dy[Dir];

            // 불인지 사람인지에 따라 달라진다.
            if (Type == true)
            {
                //사람이라면 범위밖에 나간거면 빠져나왔다는 의미이다.
                if (NextX < 0 || NextY < 0 || NextX >= X || NextY >= Y)
                {
                    _Count = _Dist[Cur.first][Cur.second] + 1;
                    return true;
                }
                
                if (_Board[NextY][NextX] == '#' || _Board[NextY][NextX] == '*' || _PlayerVisit[NextY][NextX] == true)
                    continue;

                qPair.push({ NextY, NextX });
                qJudgment.push(true);
                _PlayerVisit[NextY][NextX] = true;
                _Dist[NextY][NextX] = _Dist[Cur.first][Cur.second] + 1;
            }

            else
            {
                // 불이 아래와 같은 상황이라면 범위를 넘은것이기 때문에 취소
                if (NextX < 0 || NextY < 0 || NextX >= X || NextY >= Y)
                    continue;

                if (_Board[NextY][NextX] == '#' || _Board[NextY][NextX] == '*' || _FireVisit[NextY][NextX] == true)
                    continue;

                _Board[NextY][NextX] = '*';
                qPair.push({ NextY, NextX });
                qJudgment.push(false);
                _FireVisit[NextY][NextX] = true;
            }
        }
    }

    return false;
}

int main()
{
    int TestCase;

    cin >> TestCase;

    for (int i = 0; i < TestCase; ++i)
    {
        int X, Y;
        int Count = 0;
        cin >> X >> Y;

        vector<string> Board;
        vector<vector<bool>> PlayerVisit(Y, vector<bool>(X));
        vector<vector<bool>> FireVisit(Y, vector<bool>(X));
        vector<vector<int>> Dist(Y, vector<int>(X, -1));

        BoardFill(Board, X, Y);

        if(BFS(Board, PlayerVisit, FireVisit, Dist, X, Y, Count))
            cout << Count << '\n';
        else
            cout << "IMPOSSIBLE\n";
    }

    return 0;
}