백준 5427. 불 (bfs)

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

5427번: 불

bfs 문제이다. 

 

1. 특징

1) 시작점이 여러개인 bfs

2) 시작점이 두종류인 bfs

 

2. 삽질 포인트

2-1) 처음에 플레이어를 움직이는 bfs 코드에서, (i, j)좌표에 불이 먼저 도착한 경우는 플레이어가 해당 좌표에 갈 수 없게 했다. 

if((firemap[nx][ny] <= playermap[curx][cury] + 1)) continue;

하지만 이 경우, (i, j)에 불도 플레이어도 안간경우 if(0 <= 1) 이 되어, 플레이어는 이좌표에 방문하지 않는다. 

따라서, 코드를 다음과 같이 고쳐야한다. 

if((firemap[nx][ny] <= playermap[curx][cury] + 1) && firemap[nx][ny] > 0) continue;

불이 간 경우 && 플레이어가 나중에 도착했다면, 플레이어는 해당 좌표에 방문하지 않는다. 

 

2-2) 초기화: 나는 불과 플레이어의 처음 위치를 받아서 해당 좌표를 0으로 표시했다. (배열의 초기값도 0) 

//불 위치
for(int i = 0; i < h; i++)
{
    for(int j = 0; j < w; j++)
    {
        if(board[i][j] == '*')
        {
            _fire.push(make_pair(i, j));
            firemap[i][j] = 0;
        }
    }
}

이 경우 firemap[i][j](불이 i, j에 도달할 때의 시간) = 0인 경우, 처음 위치인지 아니면 배열의 초기값인지 알수없어서, 오류가 났다. 그래서 다음과 같이 코드르 바꾸었다. (불과 플레이어의 처음 위치를 받아서 해당 좌표를 1로 표시)

//불 위치
for(int i = 0; i < h; i++)
{
    for(int j = 0; j < w; j++)
    {
        if(board[i][j] == '*')
        {
            _fire.push(make_pair(i, j));
            firemap[i][j] = 1;
        }
    }
}

 

3. 코드

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int t;
int w, h;
string board[1002];

int dx[4] = {0, 0, -1, 1}; // 좌 우 위 아래
int dy[4] = {-1, 1, 0, 0};

int firemap[1002][1002]; // firemap[i][j] = 불이 (i, j)에 도달할 때의 시간
int playermap[1002][1002]; // playermap[i][j] = 플레이어가 (i, j)에 도달할 때의 시간
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while(t--)
    {
        cin >> w >> h;
        
        for(int i = 0; i < h; i++)
        {
            cin >> board[i];
        }

        queue<pair<int, int>> _fire;
        queue<pair<int, int>> _player;  

		//맵 초기화
        for(int i = 0; i < h; i++)
        {
            fill(firemap[i], firemap[i]+ w, 0);
            fill(playermap[i], playermap[i]+ w, 0);
        }
        
        //처음 불 위치
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                if(board[i][j] == '*')
                {
                    _fire.push(make_pair(i, j));
                    firemap[i][j] = 1;
                }
            }
        }
        //처음 상근이 위치
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                if(board[i][j] == '@')
                {
                    _player.push(make_pair(i, j));
                    playermap[i][j] = 1;
                }
            }
        }
		
        //불 번지는 bfs
        while(!_fire.empty())
        {
            int curx = _fire.front().first;
            int cury = _fire.front().second;
            _fire.pop();

            for(int dir = 0; dir < 4; dir++)
            {
                int nx = curx + dx[dir];
                int ny = cury + dy[dir];

                if(nx < 0 || nx > h-1|| ny < 0 || ny > w-1) continue; //좌표 넘어가면
                if(board[nx][ny] == '#') continue; // 벽이면
                if(firemap[nx][ny] > 0) continue; // 이미 왔으면
                _fire.push(make_pair(nx, ny)); 
                firemap[nx][ny] = firemap[curx][cury] + 1; // 저번좌표까지 불 도달한 시간 + 1
            }
        }


        bool isP = false;
        while(!_player.empty())
        {
            int curx = _player.front().first;
            int cury = _player.front().second;
            _player.pop();

            if(curx == 0 || curx == h-1 || cury ==0 || cury == w-1) // 출구에 도달했으면
            {
                cout << playermap[curx][cury]<< '\n';
                isP = true;
                break;
                
            }
            for(int dir = 0; dir < 4; dir++)
            {
                int nx = curx + dx[dir];
                int ny = cury + dy[dir];

                if(nx < 0 || nx > h-1|| ny < 0 || ny > w-1) continue;
                if(board[nx][ny] == '#') continue;
                if((firemap[nx][ny] <= playermap[curx][cury] + 1) && firemap[nx][ny] > 0) continue; // 불이 도달한 좌표이면서, 플레이어보다 빨리 도달했으면
                if(playermap[nx][ny] > 0) continue; 
                _player.push(make_pair(nx, ny));
                playermap[nx][ny] = playermap[curx][cury] + 1;
            }
        }

        if(isP == false)
            cout << "IMPOSSIBLE\n";

    }

}