[백준] 4179번. 불!

[문제]

 

www.acmicpc.net/problem/4179

4179번: 불!

 

[풀이]

 

지훈이가 미로를 빠져나오는데 최소 시간을 구하는 문제로 아래 문제와 굉장히 유사하여 쉽게 접근할 수 있었다.

www.acmicpc.net/problem/5427

5427번: 불

불도 매초마다 상,하,좌,우로 퍼지고 지훈이도 상,하,좌,우로 움직일 수 있으므로 BFS를 사용해서 풀었다.

불과 지훈이는 매초마다 움직이므로 BFS함수에서 불이 먼저 퍼지고, 지훈이가 이동하도록 구현을 하였다.

 

불의 좌표는 fire 변수에 저장하고, 지훈이의 좌표는 person에 저장하여 person이 empty가 아닐 때까지 while 문을 반복하도록 하였다.

person이 empty가 되어 while을 빠져나온다면 지훈이가 탈출할 방법이 없는 것이므로  "IMPOSSIBLE"을 출력하면서 BFS 함수를 끝내도록 하였다,

또한 지훈이의 위치가 가장자리일 경우 탈출을 할 수 있으므로 visited의 저장된 값을 출력하고 BFS 함수를 끝내도록 하였다.

 

 

[코드]

 

시간 :88ms

 

#include <iostream>
#include <queue>
#define MAX 1001

using namespace std;

struct pos{
    int x,y;
};
     
queue <pos> fire;
queue <pos> person;

int N,M;
int map[MAX][MAX]={0,};
int visited[MAX][MAX]={0,};

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

void BFS()
{
    while(!person.empty()){
        
        int fnum = fire.size();
        int pnum = person.size();
        
        while(fnum){
            fnum--;
            int x = fire.front().x;
            int y = fire.front().y;
            
            fire.pop();
            
            for(int i=0;i<4;i++){
                
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx<0||ny<0||nx>=N||ny>=M||map[nx][ny]!=0)    continue;
                
                fire.push({nx,ny});
                map[nx][ny] = 1;
            }
        }
        
        while(pnum){
            pnum--;
            int x = person.front().x;
            int y = person.front().y;
            
            person.pop();
            if(x == 0 || y ==0 || x==N-1 || y ==M-1) {
                cout << visited[x][y];
                return;
            }
            
            for(int i=0;i<4;i++){
                
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx<0||ny<0||nx>=N||ny>=M||map[nx][ny]!=0||visited[nx][ny]!=0)    continue;
                
                person.push({nx,ny});
                visited[nx][ny] = visited[x][y]+1;
            }
        }
    }
    
    cout << "IMPOSSIBLE";
    return;
}

int main(void)
{
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            if(ch == '#')   map[i][j]=-1;
            else if(ch == 'F'){
                fire.push({i,j});
                map[i][j]=1;
            }
            else if(ch == 'J') {
                person.push({i,j});
                visited[i][j]=1;
            }
        }
    }
    BFS();
    
    return 0;
}