[BaekJoon] 5427 불 (Java)

1.  문제 링크

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

2.  문제

요약

• 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 건물의 일부에는 불이 났으며, 상근이는 출구를 향해 뛰고 있습니다.
• 매 초마다, 불은 동서남북 방향의 인접한 빈 공간으로 퍼져나가는데, 벽에는 불이 붙지 않습니다.
• 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸립니다.
• 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없습니다.
• 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있습니다.
• 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 100보다 작거나 같은 테스트 케이스의 개수가 주어지고 각 테스트 케이스의 첫 번째 줄에 1보다 크거나 같고 1000보다 작거나 같은 빌딩 지도의 너비와 높이 w와 h가 주어지며 두 번째 줄부터 h개의 줄에는 w개의 문자인 빌딩의 지도가 주어집니다.
  • '.' : 빈 공간
  • '#' : 벽
  • '@' : 상근이의 시작 위치
  • '*' : 불
  • 각 지도에 @의 개수는 하나입니다.
• 출력: 각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력합니다. 만약 빌딩을 탈출할 수 없을 경우 "IMPOSSIBLE"을 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static Reader scanner = new Reader();
	static int r, c, T;
	static char[][] map;
	static int[] start, dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static LinkedList<int[]> fires;
	static int[][] time, fireTime;
	static void input() {
		c = scanner.nextInt();
		r = scanner.nextInt();
		map = new char[r][c];
		time = new int[r][c];
		fireTime = new int[r][c];
		fires = new LinkedList<>();
		for(int row = 0; row < r; row++) {
			Arrays.fill(time[row], Integer.MAX_VALUE);
			Arrays.fill(fireTime[row], Integer.MAX_VALUE);
			String input = scanner.nextLine();
			for(int col = 0; col < c; col++) {
				map[row][col] = input.charAt(col);
				if(map[row][col] == '@') {
					map[row][col] = '.';
					time[row][col] = 0;
					start = new int[] {row, col};
				}
				else if(map[row][col] == '*') {
					fireTime[row][col] = 0;
					fires.add(new int[] {row, col});
				}
			}
		}
	}
	
	static void solution() {
		Queue<int[]> loc = new LinkedList<>();
		loc.offer(start);
		int t = 0;
		while(!loc.isEmpty()) {
			int[] cur = loc.poll();
			if(time[cur[0]][cur[1]] == t) {
				spreadFire();
				t++;
			}
			for(int dir = 0; dir < 4; dir++) {
				int cx = cur[0] + dx[dir], cy = cur[1] + dy[dir];
				if(cx < 0 || cx >= r || cy < 0 || cy >= c) {
					sb.append(time[cur[0]][cur[1]] + 1).append('\n');
					return;
				}
				if(map[cx][cy] == '.') {
					if(time[cx][cy] > (time[cur[0]][cur[1]] + 1)) {
						time[cx][cy] = time[cur[0]][cur[1]] + 1;
						loc.offer(new int[] {cx, cy});
					}
				}
			}
		}
		sb.append("IMPOSSIBLE").append('\n');
	}
	
	static void spreadFire() {
		int size = fires.size();
		if(size == 0) return;
		int t = fireTime[fires.getFirst()[0]][fires.getFirst()[1]];
		Queue<int[]> fireLoc = new LinkedList<int[]>();
		for(int count = 0; count < size; count++) {
			fireLoc.offer(fires.getFirst());
			fires.remove(0);
 		}
		while(!fireLoc.isEmpty()) {
			int[] cur = fireLoc.poll();
			if(fireTime[cur[0]][cur[1]] > t) return;
			for(int dir = 0; dir < 4; dir++) {
				int cx = cur[0] + dx[dir], cy = cur[1] + dy[dir];
				if(cx >= 0 && cx < r && cy >= 0 && cy < c) {
					if(map[cx][cy] == '.' && fireTime[cx][cy] > fireTime[cur[0]][cur[1]] + 1) {
						map[cx][cy] = '*';
						fireTime[cx][cy] = fireTime[cur[0]][cur[1]] + 1;
						fireLoc.offer(new int[] {cx, cy});
						fires.add(new int[] {cx, cy});
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		T = scanner.nextInt();
		while(T-- > 0) {
			input();
			solution();
		}
		System.out.println(sb);
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}