[백준/BOJ] 5427번 불 자바 풀이

https://www.acmicpc.net/problem/5427

5427번: 불

문제

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

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

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

입력

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

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

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

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

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

출력

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

 

 

BFS를 이용해 풀 수 있는 골드4 문제다.

 

BFS는 너비 우선 탐색이므로,

0초의 상근이의 위치를 먼저 탐색하고, 1초의 상근이의 위치, 2초, 3초 ... 순서대로 탐색하게 된다.

0초에서 1초로 바뀔 때 불이 옮겨지고, 1초에서 2초로 바뀔 때 불이 옮겨진다.

먼저 입력으로 주어진 불의 위치를 fire라는 큐에 저장하고,

0초일 때 fire에 있는 불의 위치를 모두 꺼내서 상하좌우로 이동하며 *로 바꿔준다.

 

그러면 0초의 상근이는 불이 붙은 곳과 불이 붙으려는 곳에 이동할 수 없게 된다.

 

 

0초에서 1초로 바뀔 때에도 불이 옮겨질 것이므로

*로 바꾸는 불의 위치를 또 fire라는 큐에 저장해야 한다.

불이 옮겨졌다고 처리할 때마다 fire에 넣는다면, 

반복문의 종료조건이 isEmpty()이므로 빌딩이 불로 가득찰 때까지 불이 옮겨질 것이다.

즉, 0초일 때는 0초에 존재하는 불만 옮겨지고,

1초일 때는 1초에 존재하는 불만 옮겨져야 한다.

 

그러기 위해서는 *로 바꾸는 불의 위치를 temp라는 ArrayList에 임시적으로 저장해둔다.

preTime에 이전의 시간을 저장하고 preTime과 현재 큐에서 꺼낸 nowTime이 달라졌다면, (1초의 시간이 흘렀다면)

temp에 있는 값들을 fire에 넣고 다시 불을 옮긴다.

 

이 과정을 상근이가 탈출할 때까지 반복한다.

상근이가 이동하는 것은 일반 BFS로 최소 이동횟수를 찾는 것과 마찬가지로 상하좌우로 이동하면서

빌딩을 벗어나지 않고 벽이나 불이 아닌곳, 이미 방문하지 않은 곳을 방문하면서 큐에 넣으면 된다.

 

상근이가 building 배열의 외곽에 있다면 탈출할 수 있다는 것이므로

StringBuilder에 nowTime + 1을 append하고 BFS를 종료한다.

(+1을 해주는 이유는 외곽에서 한번 더 밖으로 이동해야 탈출하는 것이기 때문)

 

만약 가능한 모든 곳을 방문할 때까지 탈출하지 못했다면

while문 안에서 return되는 것이 아닌 while문이 종료될 것이므로

while문 바깥에는 StringBuilder에 IMPOSSIBLE을 append하는 코드를 적는다.

 

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

public class Main {
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static StringBuilder sb = new StringBuilder();
	static Queue<int[]> fire;
	static char[][] building;
	static boolean[][] visit;
	static int T, w, h;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for(int i=0;i<T;i++) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			fire = new LinkedList<>();
			building = new char[h][w];
			visit = new boolean[h][w];
			
			int startR = 0, startC = 0;
			for(int j=0;j<h;j++) {
				String str = br.readLine();
				for(int k=0;k<w;k++) {
					building[j][k] = str.charAt(k);
					if(building[j][k] == '@') {
						startR = j;
						startC = k;
					}
					else if(building[j][k] == '*') 
						fire.offer(new int[] {j, k});
				}
			}
			
			BFS(startR, startC);
		}
		
		System.out.println(sb);
	}
	
	static void BFS(int startR, int startC) {
		Queue<Escape> q = new LinkedList<>();
		ArrayList<int[]> temp = new ArrayList<>();
		int preTime = 0;
		
		visit[startR][startC] = true;
		q.offer(new Escape(startR, startC, 0));
		
		while(!q.isEmpty()) {
			Escape now = q.poll();
			
			if(now.time != preTime) { // 같은 시간의 위치를 모두 탐색한 경우 불을 붙이기 위해 fire에 추가
				fire.addAll(temp);
				temp.clear();
			}
			
			while(!fire.isEmpty()) { // 불이 붙으려는 칸으로 이동할 수 없으므로 미리 불 붙을 곳을 체크
				int[] f = fire.poll();
				for(int i=0;i<4;i++) {
					int fR = f[0] + dir[i][0];
					int fC = f[1] + dir[i][1];
					
					if(checkFire(fR, fC)) {
						building[fR][fC] = '*';
						temp.add(new int[] {fR, fC}); // 다음 시간에 불을 옮기기 위해 미리 저장해둠
					}
				}
			}
			
			if(checkEscape(now.r, now.c)) {
				sb.append(now.time + 1).append('\n');
				return;
			}
			
			for(int i=0;i<4;i++) {
				int nextR = now.r + dir[i][0];
				int nextC = now.c + dir[i][1];
				
				if(checkNext(nextR, nextC)) {
					visit[nextR][nextC] = true;
					q.offer(new Escape(nextR, nextC, now.time + 1));
				}
			}
			
			preTime = now.time;
		}
		
		sb.append("IMPOSSIBLE").append('\n');
	}
	
	static boolean checkFire(int r, int c) {
		if(r < 0 || r >= h || c < 0 || c >= w || building[r][c] != '.')
			return false;
		
		return true;
	}
	
	static boolean checkNext(int r, int c) {
		if(r < 0 || r >= h || c < 0 || c >= w || visit[r][c] || building[r][c] != '.')
			return false;
		
		return true;
	}
	
	static boolean checkEscape(int r, int c) {
		if(r == 0 || r == h - 1 || c == 0 || c == w - 1)
			return true;
		
		return false;
	}
	
	static class Escape {
		int r, c, time;
		Escape(int r, int c, int time) {
			this.r = r;
			this.c = c;
			this.time = time;
		}
	}

}