백준 5427번 불 [JAVA]

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w, h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

 

 

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

 

예제

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_BJ_5427_불 {
    
    static class info{
        int x, y , time;
 
        public info(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
    
    static char [][]map;
    static int w,h, answer;
    static boolean [][] visited;
    static Queue<info> fire;
    static Queue<info> person;
    static int [] dx = {-1,0,1,0}; 
    static int [] dy = {0,1,0,-1};
 
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=0;tc<T;tc++) {
            st = new StringTokenizer(br.readLine()," ");
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            
            map = new char[h][w];
            visited = new boolean[h][w];
            
            fire = new LinkedList<>();
            person = new LinkedList<>();
            
            for(int i=0;i<h;i++) {
                String str = br.readLine();
                for(int j=0;j<w;j++) {
                    map[i][j]= str.charAt(j);
                    if(map[i][j]=='@') person.offer(new info(i,j,0));
                    else if(map[i][j]=='*') fire.offer(new info(i,j,0));
                }
            }
            
            answer =0;
            bfs();
            if(answer==0) sb.append("IMPOSSIBLE\n");
            else sb.append(answer+"\n");
        }
        System.out.println(sb.toString());
    }
    
    public static void bfs() {
        
        
        while(!person.isEmpty()) {
            int size = fire.size();
            for(int i=0;i<size;i++) {
                info temp = fire.poll();
                for(int d=0;d<4;d++) {
                    int nx = temp.x+dx[d];
                    int ny = temp.y+dy[d];
 
                    if(range(nx,ny) && (map[nx][ny]=='.' || map[nx][ny]=='@')){
                        map[nx][ny]='*';
                        fire.offer(new info(nx,ny,0));
                    }
                }
            }
            
            size = person.size();
            for(int i=0;i<size;i++) {
                info temp = person.poll();
                for(int d=0;d<4;d++) {
                    int nx = temp.x+dx[d];
                    int ny = temp.y+dy[d];
                    
                    if(!range(nx,ny)) {
                        answer = temp.time+1;
                        return;
                    }
                    
                    if(map[nx][ny]=='.'){
                        map[nx][ny]='@';
                        person.offer(new info(nx,ny,temp.time+1));
                    }
                    
                }
            }
        }    
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<h && y<w;
    }
 
}

 

 

풀이 방법

빌딩의 지도가 주어졌을 때, 상근이가 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 문제였습니다.

저는 상근이 위치정보를 person큐와 불의 위치정보를 fire큐에 넣어주었습니다.

불과 상근이는 동시에 움직이므로 bfs를 이용해 불을 먼저 움직인 뒤, 상근이를 움직였습니다. 만약 상근이가 다음 움직일 위치가 배열의 범위를 넘어선다면 출구로 빠져나간 것이므로 리턴을 통해 걸린 시간을 반환해주었습니다.