[BaekJoon] 4179 불! (Java)

1.  문제 링크

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

2.  문제

요약

• 지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로 이동합니다.
• 불은 각 지점에서 네 방향으로 확산됩니다.
• 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있습니다.
• 지훈이와 불은 벽이 있는 공간은 통과하지 못합니다.
• 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기 전에 탈출할 수 있는지의 여부 및 얼마나 빨리 탈출할 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1000보다 작거나 같은 정수인 미로 행의 개수 R과 열의 개수 C가 주어지고 두 번째 줄부터 R개의 줄에는 각각의 미로 행이 주어집니다. 각 문자들은 다음을 뜻합니다.
  • # : 벽
  • . : 지나갈 수 있는 공간
  • J : 지훈이의 미로에서의 초기 위치(지나갈 수 있는 공간)
  • F : 불이 난 공간
  • J는 입력에서 하나만 주어집니다.
• 출력: 지훈이가 불이 도달하기 전에 미로를 탈출할 수 없는 경우 IMPOSSIBLE을 출력합니다. 지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력합니다.

3.  소스코드

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 R, C;
	static char[][] map;
	static int[] start, dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static int[][] times;
	static LinkedList<int[]> fires;
	static void input() {
		Reader scanner = new Reader();
		R = scanner.nextInt();
		C = scanner.nextInt();
		map = new char[R][C];
		times = new int[R][C];
		fires = new LinkedList<>();
		for(int row = 0; row < R; row++) {
			String info = scanner.nextLine();
			for(int col = 0; col < C; col++) {
				map[row][col] = info.charAt(col);
				times[row][col] = Integer.MAX_VALUE;
				if(map[row][col] == 'J') {
					start = new int[] {row, col};
					map[row][col] = '.';
					times[row][col] = 0;
				} else if(map[row][col] == 'F') fires.add(new int[] {row, col});	
			}
		}
	}
	
	static void solution() {
		Queue<int[]> loc = new LinkedList<>();
		loc.offer(start);
		int time = 0;
		while(!loc.isEmpty()) {
			int[] cur = loc.poll();
			if(times[cur[0]][cur[1]] == time) {
				spreadFire();
				time++;
			}
			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) {
					System.out.println(times[cur[0]][cur[1]] + 1);
					return;
				}
				if(isInMap(cx, cy)) {
					if(map[cx][cy] == '.' && times[cx][cy] > times[cur[0]][cur[1]] + 1) {
						times[cx][cy] = times[cur[0]][cur[1]] + 1;
						loc.offer(new int[] {cx, cy});
					}
				}
			}
		}
		System.out.println("IMPOSSIBLE");
	}
	
	static void spreadFire() {
		int size = fires.size();
		for(int count = 0; count < size; count++) {
			int[] cur = fires.get(0);
			fires.remove(0);
			for(int dir = 0; dir < 4; dir++) {
				int cx = cur[0] + dx[dir], cy = cur[1] + dy[dir];
				if(isInMap(cx, cy)) {
					if(map[cx][cy] == '.') {
						fires.add(new int[] {cx, cy});
						map[cx][cy] = 'F';
					}
				}
			}
		}
	}
   
	static boolean isInMap(int x, int y) {
		if(x >= 0 && x < R && y >= 0 && y < C) return true;
		return false;
	}
   
	public static void main(String[] args) {
		input();
		solution();
	}

	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;
		}
	}
}