[백준] 5427번. 불

[문제]

 

www.acmicpc.net/problem/5427

5427번: 불

[풀이]

 

매 초마다 불은 상,하,좌,우 방향으로 퍼져 나간다.

이 때 상근이가 탈출하는데 걸리는 시간을 구하는 문제이다.

 

처음에는 불이 퍼지는 함수랑 상근이가 움직이는 함수를 따로 만들어서 풀었다.

DFS를 사용해 상근이가 움직이도록 했는데, DFS로 움직일 때마다 map을 저장하기 위해 배열을 하나 더 지역변수로 선언했다.

하지만 map의 크기가 워낙 커서 계속 오류가 났다.

 

두번째 방법으로 BFS 함수에서 불이 퍼지는 것과 상근이가 움직이는 것을 모두 구현했다.

 

처음에는 불이 퍼지는 것을 그냥 반복문으로 돌면서 불을 만나면 상,하,좌,우로  퍼지도록 구현했다.

하지만 시간초과가 나와서 불이 퍼지는 것도 BFS로 queue를 사용해 풀었다.  

 

불이 퍼지고 상근이가 움직이는 것을 구현하기 위해  queue의 size만큼 while문을 반복하도록 구현하였다. 

 

 

[코드]

 

시간 : 176ms

 

#include <iostream>
#include <cstring>
#include <queue>

#define MAX 1001

using namespace std;

struct pos{
    int x,y;
};

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

pos start;
int visited[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int w,h;
int res=0;

queue <pos> fq;

void BFS()
{
    queue <pos> q;
    
    q.push(start);
    visited[start.x][start.y]=1;
    
    while(!q.empty()){
        
        int _size = q.size();
        int fsize = fq.size();
        
        while(fsize--){
            int x = fq.front().x;
            int y = fq.front().y;
            
            fq.pop();
            
            for(int i=0;i<4;i++){
                
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx<0 || ny<0 || nx>=w || ny >= h || map[nx][ny]!= 0 || visited[nx][ny] != 0)  continue;

                map[nx][ny]=1;
                visited[nx][ny]=-1;
                fq.push({nx,ny});
            }
        }
        
        while(_size--){
        
            int x = q.front().x;
            int y = q.front().y;
            
            q.pop();
            
            for(int i=0;i<4;i++){
                
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx<0 || ny<0 || nx>=w || ny >= h){
                    res = visited[x][y];
                    return;
                }
                
                if(map[nx][ny]!= 0 || visited[nx][ny]!=0)  continue;

                visited[nx][ny]=visited[x][y]+1;
                q.push({nx,ny});
                            
            }
        }
    }
}


int main(void)
{
    int T;
    cin >> T;
    
    for(int k=0;k<T;k++)
    {
        memset(visited, false, sizeof(visited));
        memset(map, false, sizeof(map));

        while(!fq.empty())  fq.pop();
        
        cin >> h >> w;
        res=0;
        
        for(int i=0;i<w;i++){
            for(int j=0;j<h;j++){
                
                char ch;
                cin >> ch;
                
                if( ch == '@')  start={i,j};
                else if( ch == '*') {
                    map[i][j]=1;
                    visited[i][j]=-1;
                    fq.push({i,j});
                }
                else if( ch == '#') map[i][j]=1;
                
            }
        }
        
        BFS();
        
        if(res==0)  cout << "IMPOSSIBLE";
        else    cout << res;
        
        cout << "\n";
    }
    
    return 0;
}