[BOJ] 백준 5427번 불 (Java)

• #5427 불
• 문제 풀이  
  • 설계
• 풀이 코드 

#5427 불

난이도 : 골드 4

유형 : 그래프 탐색 / BFS / 구현

5427번: 불

▸ 문제

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

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

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

▸ 입력

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

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

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

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

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

▸ 출력

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

 

문제 풀이  

처음에 접근한 방식은 불번지는 시간을 map[][]배열에 표기하여 시간별로 통과할 수 있게 작성하였다. 예를들면, 3초에 번진 불은 1~3초안에 지나면 통과할 수 있다. 그러나 25%까지 통과하고 시간초과가 발생했다. 매번 상근이는 똑같은 시작점에서 출발을 하니 최악의 케이스의 경우 통과하지 못한 것 같다. 

 

실패코드↓

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int w,h;
	static int[][] map;
	static boolean[][] check;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(tc-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			int sx= 0, sy =0;
			map = new int[h][w];
			
			int space =0;
			for(int i=0; i<h; i++) {
				String line = br.readLine();
				// #: 0, *: 7, @: 29, .: 11
				for(int j=0; j<w; j++) {
					int c = line.charAt(j)-'#';
					if(c==29) {
						sy = i;
						sx = j;
						space++;
						map[i][j] = -1;
					}else if(c==7){
						map[i][j] = 1001;
					}else if(c==11) {
						map[i][j] = -1;
						space++;
					}else {
						map[i][j] = c;
					}
				}
			}
			
			int time =1;
			if(sx==0 || sx==w-1 || sy==0 || sy==h-1) {
				sb.append(1+"\n");
			}else {
				List<int[]> person = new ArrayList<>();
				person.add(new int[] {sx,sy});
				out : while(true) {
					// 1. 불 번짐 
					check = new boolean[h][w];
					int newFire = 0;
					for(int i=0; i<h; i++) {
						for(int j=0; j<w; j++) {
							if(map[i][j] ==0) continue;
							if(!check[i][j] && 
									(map[i][j] == time-1 ||map[i][j] == 1001)) {
								newFire += fireMove(j,i, time);
							}
						}
					}
					
					// 2. 상근 이동 (1번 불번짐 영향 x, 그러나 번질 곳으로 이동은 x)
					int res=0;
					for(int[] pos : person) {
						 res = escape(pos[0], pos[1], time);
						 if(res== 1) {
								sb.append((time+1)+"\n");
								break out;
							}
					}
					if(newFire ==0 || time>w*h) {
						sb.append("IMPOSSIBLE\n");
						break;
					}
					time++;
				}
			}
		}
		System.out.println(sb.toString());
	}
	
	static int escape(int x, int y, int time) {
		Queue<int[]> q = new LinkedList<>();
		check = new boolean[h][w];
		q.add(new int[] {x,y,1});
		check[y][x] = true;
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int px = p[0];
			int py = p[1];
			int move = p[2];
			
			if(px==0 || px==w-1 || py==0 || py==h-1) {
				return 1;
			}
			if(move> time) return -1;
			for(int i=0; i<4; i++) {
				int nx = px + dx[i];
				int ny = py + dy[i];
				
				if(nx<0 || nx>w-1 || ny<0 || ny>h-1) continue;
				if(check[ny][nx] || map[ny][nx] == 0 || map[ny][nx] == 1001) continue;
				
				if(map[ny][nx] ==-1 || map[ny][nx] >= move) {
					check[ny][nx] = true;
					q.add(new int[] {nx, ny, move+1});
				}
			}
		}
		return -1;
	}
	
	static int fireMove(int x, int y, int time) {
		int cnt=0;
		check[y][x] = true;
		int px = x;
		int py = y;
		
		for(int i=0; i<4; i++) {
			int nx = px+dx[i];
			int ny = py+dy[i];
			
			if(nx<0 || nx>w-1 || ny<0 || ny>h-1) continue;
			if(check[ny][nx]) continue;
			
			// 빈공간 , 상근 위치 
			if(map[ny][nx] == -1) {
				check[ny][nx] = true;
				map[ny][nx] = time;
				cnt++;
			}
		}
		return cnt;
	}
}

 

그래서 상근이의 위치 상태와 불의 위치 상태를 좀 더 동적으로 접근했다. Queue를 이용하여 매 시간별로 각 상태를 체크해주었다. 위의 방식으로 접근했던 이유는 불과 상근이의 위치가 겹치게 되는 부분 처리가 가능할까라는 생각이 들었기 때문인데, 두 개의 Queue를 생성하여 한 싸이클에 각자의 위치를 저장하고 있으면 현재 상근이의 위치에 불이 번지더라도 Queue에 상근의 위치가 있기 때문에 탐색이 가능했다.

 

설계

1. fire, person의 위치를 저장하는 두 개의 Queue를 생성하여 정보를 저장한다. 
2. 싸이클을 돌린다. 만약 상근이의 Queue가 비게된다면 더이상 움직일 수 없으므로 반복문을 종료한다. if(person.isEmpty()) break;
   1. 첫 번째로, 불 번지기 메서드를 동작한다. fireMarking(px, py);
      1. 현재 불의 상하좌우로 이동한 다음 다시 fire queue에 저장한다. fire.add(new int[] {nx,ny});
   2. 그 다음으로, 상근 이동하기 메서드를 동작한다. escape(px, py, time);
      1. 빈공간'.'으로 상근이를 이동시킨 다음 person queue에 저장한다. person.add(new int[] {nx, ny, time+1});
      2. 만약 그래프 범위를 벗어나게된다면 탈출을 성공한 것이므로 싸이클을 종료한다.

 

풀이 코드 

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 {
	static int w,h;
	static char[][] map;
	static Queue<int[]> person;
	static Queue<int[]> fire;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(tc-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			map = new char[h][w];
			fire = new LinkedList<>();
			person = new LinkedList<>();
			for(int i=0; i<h; i++) {
				String line = br.readLine();
				for(int j=0; j<w; j++) {
					char c = line.charAt(j);
					if(c=='@') {
						person.add(new int[] {j,i,0});
					}else if(c=='*') {
						fire.add(new int[] {j,i});
					}
					map[i][j] = c;
				}
			}
			int res= -1;
			out : while(true) {
				// 1. 불 번짐
				int fSize = fire.size();
				for(int i=0; i<fSize; i++) {
					int[] pos = fire.poll();
					int px = pos[0], py = pos[1];
					fireMarking(px, py);
				}
				
				// 2. 상근 이동 (1번 불번짐 영향 x, 그러나 번질 곳으로 이동은 x)
				int pSize = person.size();
				for(int i=0; i<pSize; i++) {
					int[] pos = person.poll();
					int px = pos[0], py = pos[1], time =pos[2];
					res = escape(px, py, time);
					if(res != -1) {
						break out;
					}
				}
				if(person.isEmpty()) break;
			}
			
			if(res !=-1) sb.append(res+"\n");
			else sb.append("IMPOSSIBLE\n");
		}
		System.out.println(sb.toString());
	
	}
	
	static int escape(int x, int y, int time) {
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx<0 || nx>w-1 || ny<0 || ny>h-1) {
				return time+1;
			}
			
			if(map[ny][nx] == '.') {
				map[ny][nx] = '@';
				person.add(new int[] {nx, ny, time+1});
			}
		}
		return -1;
		
	}
	
	static void fireMarking(int x, int y) {
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx<0 || nx>w-1 || ny<0 || ny>h-1) continue;
			
			// 빈공간 , 상근 위치 
			if(map[ny][nx] == '.' || map[ny][nx] == '@') {
				map[ny][nx] = '*';
				fire.add(new int[] {nx,ny});
			}
		}
	}
}