[백준] 4179. 불!

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

4179번: 불!

---

[ 문제 풀이 ]

저는 지훈이와 불이 상, 하, 좌, 우 네 방향으로 움직일 수 있기 때문에 Queue 를 사용하였습니다. 이 문제에서는 지훈이와 불이 퍼지는 순서가 중요한데, 저는 먼저 불과 지훈이를 퍼뜨리는데 spread 라는 BFS 형식의 함수 하나를 사용했습니다.

spread의 두 번째 매개변수로 불이면 F, 진수면 J 를 넣어서 만약에 F 이면 진수가 있는 자리와 지나갈 수 있는 공간으로 불을 퍼뜨려 줬고, J 이면 지나갈 수 있는 공간으로만 진수를 이동시켰습니다. 그래서 매번 BFS 할 때 마다 진수가 가장 자리로 이동하면 isOut 이라는 boolean 변수를 true로 만들어서 탈출했다고 표시했습니다.

진수가 가장자리에 도착했다면 반복문이 종료하는데, 시간이 한번 더 지나야 진수가 최종적으로 탈출한 것이기 때문에 마지막에 TIME+1을 정답으로 출력했습니다.

---

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 4179 불

public class Main {

	static int R, C, TIME;
	static char[][] map;
	static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static Queue<Pair> fire = new LinkedList();
	static Queue<Pair> J = new LinkedList();
	static boolean[][] visited;
	static boolean isOut;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		R = sc.nextInt();
		C = sc.nextInt();

		sc.nextLine();
		map = new char[R][C];

		for (int i = 0; i < R; i++) {
			String st = sc.nextLine();
			for (int j = 0; j < st.length(); j++) {
				map[i][j] = st.charAt(j);
				if (map[i][j] == 'J') {
					J.offer(new Pair(i, j));
					if(i == 0 || j == 0 || i == R-1 || j == C-1) {
						System.out.println(1); 
						return;
					}
				}
				else if (map[i][j] == 'F')
					fire.offer(new Pair(i, j));
			}
		}
		
		boolean flag = false;
		
		while(true) {

			// 불 퍼뜨리기
			spread(fire, 'F');
			
			
			// 지훈이 움직이기
			spread(J, 'J');
		
			TIME++;
	
			if(isOut) {
				flag = true;
				break;
			}
			if(J.isEmpty()) break;
			
		}
		
		if(flag) System.out.println(TIME+1);
		else System.out.println("IMPOSSIBLE");

	}

	public static void spread(Queue<Pair> queue, char data) {
		visited = new boolean[R][C];

		int len = queue.size();

		for (int i = 0; i < len; i++) {
			Pair p = queue.poll();

			for (int j = 0; j < 4; j++) {
				int nx = p.x + dir[j][0];
				int ny = p.y + dir[j][1];

				if (isInside(nx, ny) && !visited[nx][ny]) {
					if (data == 'F' && (map[nx][ny] == '.' || map[nx][ny] == 'J')) {
						map[nx][ny] = data;
						visited[nx][ny] = true;
						queue.offer(new Pair(nx, ny));
					} else if (data == 'J' && map[nx][ny] == '.') {
						map[nx][ny] = data;
						visited[nx][ny] = true;
						queue.offer(new Pair(nx, ny));
						if(nx == 0 || ny == 0 || nx == R-1 || ny == C-1) {
							isOut = true;
							return;
						}
					}
				}
			}
		}
	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < R && y >= 0 && y < C;
	}
}

class Pair {
	int x;
	int y;

	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}

}