[백준] 4179 불!

문제 출처: www.acmicpc.net/problem/4179

4179번: 불!

: 미로에서 일하는 지훈이가 불이 났을 때 탈출할 수 있는지, 탈출할 수 있다면 얼마나 빨리 탈출가능한지를 결정해야한다.

: BFS 방식으로 접근할 수 있고, 시간이 갈 때마다 불을 인접한 칸으로 확산시켜주고 지훈이는 이동 가능한 곳으로 갈 수 있도록 해준다. 

: 만약 지훈이가 이동하던중 종료조건인 미로의 가장자리에 가게 된다면 현재까지 소요시간을 바로 반환시켜주고, 계속해서 이동했지만 결국 더이상 이동할 수 없는 상태가 되면 -1을 반환하도록한다.

: main 메소드에서 반환값을 받아 -1일 때는 탈출할 수 없음을 나타내므로 "IMPOSSIBLE"을 출력하고 -1이 아니라면 소요시간을 출력할 수 있도록 해준다.

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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static char[][] map;
	static class Point{
		int r, c, cnt;

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	static Point me;
	static Point start;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new char[N][M];
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == 'J') q.add(new Point(i,j));
				if(map[i][j] == 'F') fq.add(new Point(i, j));
			}
		}
		int res = bfs();
		if(res == -1) System.out.println("IMPOSSIBLE");
		else System.out.println(res);
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static Queue<Point> q = new LinkedList<>();
	static Queue<Point> fq = new LinkedList<>();
	private static int bfs() {
		while(!q.isEmpty()) {
			
			int fsize = fq.size();
			
			for(int k = 0; k < fsize; k++) {
				Point fire = fq.poll();
			
				for(int i = 0; i < 4; i++) {
					int nr = fire.r + dr[i];
					int nc = fire.c + dc[i];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= M ) continue;
					if(map[nr][nc] == '#' || map[nr][nc] == 'F') continue;
					map[nr][nc] = 'F';
					fq.offer(new Point(nr, nc, fire.cnt+1));
				}
			}
			
			int size = q.size();
			for(int k = 0; k < size; k++) {
				Point cur = q.poll();

				for(int i = 0; i < 4; i++) {
					int nr = cur.r + dr[i];
					int nc = cur.c + dc[i];
					if(nr < 0 || nr >= N || nc < 0 || nc >= M) {
						return cur.cnt+1;
					}
					if(map[nr][nc] == '#' || map[nr][nc] == 'F' || map[nr][nc] == 'J')continue;
					map[nr][nc] = 'J';						
					q.offer(new Point(nr, nc, cur.cnt+1));		
				}
			}
		}
		return -1;
	}
}