[BOJ] 백준 4179번 불! (Java)

#4179 불!

난이도 : 골드 4

유형 : 그래프 탐색 / BFS

 

4179번: 불!

▸ 문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

▸ 입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

▸ 출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

 

문제 풀이  

BFS 시뮬레이션 문제로 J가 그래프 외곽으로 빠져나갈 수 있는 최단 경로를 탐색하는 문제입니다. 불번짐을 먼저 돌리고 그 다음에 지훈이가 이동할 수 있는 공간을 탐색하여 최단 경로로 탈출하면 됩니다. 저는 IMPOSSIBLE 스펠링을 잘못 입력해서 이미 맞은 문제를 오랫동안 붙잡고 있었습니다... (28%에서 틀리면 저처럼 오타일 수도 있습니다.)

• 해당 링크를 통해 B.X파일을 들어가보면 모든 반례를 테스트해볼 수 있습니다.

 

설계

1. 주어진 맵 데이터에서 지훈이의 위치와 불들의 위치를 각 큐에 저장한다.
   1. if(map[i][j] == 'J') personQ.add(new int[] {j,i,0});
   2. if(map[i][j] == 'F') fireQ.add(new int[] {j,i});
2. 지훈이가 탈출하거나 더이상 움직일 수 없을 때까지 시뮬레이션을 돌려준다.  if(personQ.isEmpty()) break;
   1. 'F'로 되어있는 지점에서 상하좌우로 벽이 아닌 공간에 불을 번지게 한다.
   2. 벽이거나 불이 번진 곳을 제외한 공간으로 지훈이를 이동시킨다.
   3. 지훈이가 만약 맵밖으로 빠져나왔다면 탐색을 종료한다.
3. 탈출했다면 최단경로를 탈출하지 못했다면 "IMPOSSIBLE"을 출력한다.

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static int r,c;
	static char[][] map;
	static Queue<int[]> fireQ, personQ;
	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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		map = new char[r][c];
		
		String line;
		fireQ = new LinkedList<>();
		personQ = new LinkedList<>();
		for(int i=0; i<r; i++) {
			line = br.readLine();
			for(int j=0; j<c; j++) {
				map[i][j] = line.charAt(j);
				if(map[i][j] == 'J') {
					personQ.add(new int[] {j,i,0});
				}else if(map[i][j] == 'F') {
					fireQ.add(new int[] {j,i});
				}
			}
		}
		
		int res = -1;
		out: while(true) {
			int fSize = fireQ.size();
			for(int i=0; i<fSize; i++) {
				int[] p = fireQ.poll();
				fireMoving(p[0], p[1]);
			}
			
			int pSize = personQ.size();
			for(int i=0; i<pSize; i++) {
				int[] p = personQ.poll();
				res = escape(p[0], p[1], p[2]);
				if(res != -1) break out;
			}
			if(personQ.isEmpty()) break;
		}
		
		if(res == -1) {
			System.out.println("IMPOSSIBLE");
		}else {
			System.out.println(res);
		}
	
	}
	
	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 || ny<0 ||  nx>c-1 || ny>r-1) {
				return time+1;
			}
			
			if(map[ny][nx] == '.') {
				map[ny][nx] = 'J';
				personQ.add(new int[] {nx, ny, time+1});
			}
		}
		return -1;
	}
	
	static void fireMoving(int x, int y) {
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || ny < 0 || nx > c-1 || ny > r-1) continue;
			
			if(map[ny][nx] == '.' || map[ny][nx] == 'J') {
				map[ny][nx] = 'F';
				fireQ.add(new int[] {nx, ny});
			}
		}
	}
}