BOJ 4179 불!

www.acmicpc.net/problem/4179

4179번: 불!

 

 

문제 분석

- 기존에 풀었던 BOJ 5427 불 문제와 똑같은 문제다.

- bfs로 탐색하면서 불을 지르고, 지훈이를 이동시킨다. 

- 각각의 좌표를 따로 관리하면서 지훈이가 탈출할 수 있도록 한다. 

 

 

문제 풀이

1) 불의 좌표와 지훈이의 좌표를 각각의 덱에 받아온다.

2) bfs를 통해 불-> 지훈이순서로 탐색을 한다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	private static int R, C, ans;
	private static int[] dr = { -1, 1, 0, 0 }; // 상하좌우 행
	private static int[] dc = { 0, 0, -1, 1 }; // 상하좌우 열
	private static char[][] map;
	private static boolean[][] visited;
	private static Deque<firePoint> fireDq; // 불의 좌표값 저장하는 큐
	private static Deque<jihunPoint> jihunDq; // 지훈이의 좌표값 저장하는 큐

	public static void main(String[] args) throws Exception {
		input();
	}// main

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new char[R][C];
		visited = new boolean[R][C];
		jihunDq = new ArrayDeque<>();
		fireDq = new ArrayDeque<>();

		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				char ch = s.charAt(j);
				map[i][j] = ch;
				if (ch == 'J') {
					jihunDq.add(new jihunPoint(i, j, 0));
					visited[i][j] = true;
					map[i][j] = '.';
				}
				if (ch == 'F')
					fireDq.add(new firePoint(i, j));
			}
		} // 좌표값 입력
		ans = bfs();
		if (R == 1 && C == 1) {
			ans = 0;
		}
		System.out.println(ans == -1 ? "IMPOSSIBLE" : ans);
	}// input

	private static int bfs() {

		while (!jihunDq.isEmpty()) {

			int size = fireDq.size();
			// 일단 불을 지르자.
			for (int i = 0; i < size; i++) {
				firePoint cur = fireDq.poll();
				int r = cur.x;
				int c = cur.y;

				for (int d = 0; d < 4; d++) {
					int nr = r + dr[d];
					int nc = c + dc[d];

					if (nr < 0 || nc < 0 || nr > R-1 || nc > C-1)
						continue;

					if (map[nr][nc] == '.') {
						map[nr][nc] = 'F';
						fireDq.add(new firePoint(nr, nc));
					}

				}
			}

			size = jihunDq.size();
			// 지훈이 이동시키고 그 자리가 불나면 종료, 불이 아니면 이동시키기.
			for (int i = 0; i < size; i++) {
				jihunPoint cur = jihunDq.poll();
				int r = cur.x;
				int c = cur.y;
				int time = cur.depth;

				if (r == 0 || c == 0 || r == R - 1 || c == C - 1) { // 지훈이가 탈출했을 경우
					ans = time + 1;
					return ans;
				}

				for (int d = 0; d < 4; d++) {
					int nr = r + dr[d];
					int nc = c + dc[d];

					if (nr < 0 || nc < 0 || nr > R-1 || nc > C-1)
						continue;

					if (visited[nr][nc])
						continue;

					if (map[nr][nc] == '.') {
						visited[nr][nc] = true;
						jihunDq.add(new jihunPoint(nr, nc, time + 1));
					}

				}
			}
		}
		return -1;
	}// bfs

	static class jihunPoint {
		int x;
		int y;
		int depth;

		public jihunPoint(int x, int y, int depth) {
			super();
			this.x = x;
			this.y = y;
			this.depth = depth;
		}
	}// jihunPoint-class

	static class firePoint {
		int x;
		int y;

		public firePoint(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}// firePoint-class

}// class-End