5427번

5427번 - 불

BFS 문제

두가지 요인을 같이 BFS를 통해서 움직여줘야 한다.

큐에 움직이는 사람과 번지는 불을 같이 넣으면서 함께 이동시켜줘야 한다. 그래서 나는 일단 사람을 이동시키고 불을 이동시키는 방법으로 

BFS를 구현해주었다.

큐는 FIFO 이라는 점을 이용하여 일단 사람의 위치를 큐에 먼저 넣어주고, 그 다음에 불의 위치를 큐에 넣어주었다.

그리고 while 문 안을 돌면서, 큐에서 꺼낸 값이 사람의 위치인가 불의 위치인가를 파악했다.

사람의 위치라면, for문을 돌면서 상하좌우에 사람을 이동시킨다. 단 사람은 ' . ' 이라는 빈 공간으로만 움직일 수 있다.

그리고 만약 사람의 위치일때 map의 가장자리에 존재한다면 탈출 할 수 있다는 뜻이므로 cango를 true로 만들고 while 문을 빠져나간다.

그리고 이때 움직인 값은 dist 를 이용하여 저장하였으므로 정답값에는 +1 을 추가하여 출력한다.

큐에서 꺼낸 값이 불의 위치 일때는 '#' 인 벽과 ' * ' 인 불을 제외하고는 상하좌우로 움직일 수 있도록 한다. 

그리고 불이 번진 곳은 ' * ' 로 문자를 변경하면서 BFS를 진행한다.

이런식으로 하면 사람이 이동-> 불이 이동-> 사람이 이동-> 불이 이동 이런식으로 구현할 수 있다.

##

항상 전역변수는 init() 함수를 만들어서 초기화 하는 것을 까먹지 말자!

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
char map[1000][1000];
int dist[1000][1000] = { 0, };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
void init()
{
    for(int i=0;i<1000;i++)
        for (int j = 0; j < 1000; j++)
        {
            //map[i][j] = '#';
            dist[i][j] = 0;
        }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    int sx, sy;
    for (int t = 1; t <= tc; t++) {
        init();
        int h, w;
        queue<pair<int, int>> q;
        cin >> w >> h;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
                //사람 위치를 큐에 넣기
                if (map[i][j] == '@')
                {
                    sx = i, sy = j;
                    q.push({ sx,sy });
                }
            }
        }
 
 
        //불을 큐에 넣기
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == '*')
                {
                    q.push({ i,j });
                }
            }
        }
 
        //끝났는지 판단하는 변수
        bool cango = false;
        int ans = 0;
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            //큐에서 꺼낸 값이 사람일 때
            if (map[x][y] == '@')
            {
                //사람이 끝점에 왔을 때 성공
                if (x == 0 || x == h-1 || y == 0 || y == w-1)
                {
                    ans = dist[x][y] + 1;
                    cango = true;
                    break;
                }
 
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx >= 0 && ny >= 0 && nx < h && ny < w && map[nx][ny] == '.')
                    {
                        //사람 위치 움직여주고 큐에 값 넣기
                        dist[nx][ny] = dist[x][y] + 1;
                        map[nx][ny] = '@';
                        q.push({ nx,ny });
                    }
                }
            }
            //큐에서 꺼낸 값이 불 일때
            else if (map[x][y] = '*')
            {
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx >= 0 && ny >= 0 && nx < h && ny < w && map[nx][ny] != '#' && map[nx][ny] != '*')
                    {
                        //불이 번지고 큐에 불이 번진 위치넣기
                        map[nx][ny] = '*';
                        q.push({ nx,ny });
                    }
                }
            }
 
        }
 
        if (cango)
            cout << ans << endl;
        else
            cout << "IMPOSSIBLE" << endl;
 
    }
 
    return 0;
}