[C++] 백준 5427번: 불

🔗문제

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

5427번: 불

 

🖍풀이

 

불 좌표, 상근이 좌표를 저장할 두 개의 queue를 생성하고 입력 받을 때 push해준다.

std::queue<std::pair<int, int>> fire;
std::queue<std::pair<int, int>> me;

 

재방문 방지 배열도 만들어 주었다.

int visited[MAX][MAX];

---

가장 중요한 BFS 탐색 방법

 

불 이동이랑 상근이 이동의 탐색에 겹치는 코드가 많아서 함수로 해결했다.

void BFS(std::queue<std::pair<int, int>>& q, const bool isFire, bool& flag)

 

🔥 불 이동

if(isFire)
{
    if(!isValid(x, y))
        continue;
    
    //불은 상근이가 갔던 경로도 태우므로 재방문 검사가 필요없다.
    if(map[x][y] == '.')
    {
        q.push({x, y});
        map[x][y] = '*'; // 불태운 곳 표시
    }
}

• 불의 이동에서 범위에 넘어가서는 안된다. 벽에는 불이 붙지 않는 이유도 있다.
• 불은 재방문 검사를 하지 않는다. 상근이가 지나갔던 곳도 걍 태워버리기 때문이다.
• 단, 아직 불이 붙지 않은 곳으로만 이동하고 map에도 화재 표시를 해준다. 상근이가 못 오는 구역이라는 걸 확실히 하기 위함이다.

 

👩🏻‍🚒 상근이 이동

if(!isValid(x, y))
{
    std::cout << visited[nowX][nowY];
    flag = true;
    return;
}

if(!visited[x][y] && map[x][y] == '.')
{
    q.push({x, y});
    visited[x][y] = visited[nowX][nowY] + 1;
}

• 상근이가 유효 범위를 넘어갔다는 것은 탈출을 의미한다.
  • 참조로 데려온 flag를 true로 변경하고 탐색을 멈춘다.
• 불이나 상근이가 방문하지 않은 빈공간이 있을 때 상근이가 갈 수 있는 경로를 추가해주고 지금까지 몇번 이동 했는지 표시 해준다.

 

출력

bool flag = 0;
while(!flag && !me.empty())
{
    BFS(fire, true, flag);
    BFS(me, false, flag);
}
std::cout << (flag ? "\n" : "IMPOSSIBLE\n");

불이 더 이상 이동할 좌표가 없다는 건 상관없지만!

상근이가 탈출도 못 했는데 더 이상 갈 곳이 없다면  탈출 실패를 뜻한다!!

 

 

 

---

도움이 된 반례

25%에서 틀렸습니다.를 보아서 백준의 질문 검색에 있는 게시글의 반례 도움을 받았다.

원인은 문제를 제대로 읽지 않아서다.

이제 불이 붙으려는 칸으로 이동할 수 없다.

 

상근이의 이동보다 불의 이동을 우선시 해야 한다.

1
3 3
###
#@.
##*
//정답: IMPOSSIBLE
//오답: 2

(들어가자 마자 25% 반례글이 있었다. 나같은 사람 많구나🥹)

 

 

 

💾 소스

#include <iostream>
#include <queue>
#include <memory.h>
#define MAX 1000

int R, C;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
char map[MAX][MAX];
int visited[MAX][MAX];

bool isValid(int a, int b)
{
    if(a>=R || b>=C || a<0 || b<0)
        return false;
    return true;
}

void BFS(std::queue<std::pair<int, int>>& q, const bool isFire, bool& flag)
{
    int qSize = q.size();
    while(qSize--)
    {
        int nowX = q.front().first;
        int nowY = q.front().second;
        q.pop();
        
        for(int i=0; i<4; ++i)
        {
            int x = nowX + dx[i];
            int y = nowY + dy[i];
            
            if(isFire)
            {
                if(!isValid(x, y))
                    continue;
                
                if(map[x][y] == '.')
                {
                    q.push({x, y});
                    map[x][y] = '*';
                }
            }
            else // 상근이 이동
            {
                if(!isValid(x, y))
                {
                    std::cout << visited[nowX][nowY];
                    flag = true;
                    return;
                }
                
                if(!visited[x][y] && map[x][y] == '.')
                {
                    q.push({x, y});
                    visited[x][y] = visited[nowX][nowY] + 1;
                }
            }
        }
    }
    
    return;
}


int main()
{
    int T=0;
    std::cin >> T;
    while(T--)
    {
        std::queue<std::pair<int, int>> fire;
        std::queue<std::pair<int, int>> me;
        memset(visited, 0, sizeof(visited));
        memset(map, NULL, sizeof(map));
        
        std::cin >> C >> R;
        for(int i=0; i<R; ++i)
        {
            for(int j=0; j<C; ++j)
            {
                std::cin >>map[i][j];
                if(map[i][j] == '*')
                    fire.push({i, j});
                else if(map[i][j] == '@')
                {
                    me.push({i, j});
                    visited[i][j] = true;
                }
            }
        }
        
        bool flag = 0;
        while(!flag && !me.empty())
        {
            BFS(fire, true, flag);
            BFS(me, false, flag);
        }
        
        std::cout << (flag ? "\n" : "IMPOSSIBLE\n");

    } //T
    return 0;
}