백준저지 4179번 불!

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

4179번: 불!

 

 

접근 방법

1. 지훈의 위치를 저장할 큐, 불의 위치를 저장할 큐, 지훈과 불의 이동을 동시에 저장할 2차원 boolean 배열을 준비한다.

입력 받을 때, 지훈과 불의 위치를 각각 큐에 넣으면서 방문했다고 표시한다. 지훈의 위치는 '.'으로 바꾼다.

2. 입력받을 때부터 지훈이 벽에 붙어있다면 1을 출력하고 끝낸다.

3. 그 외의 경우, 지훈의 큐가 빌 때까지 또는 지훈이 벽에 도달할 때까지 반복한다.

  3-1. 불의 큐 사이즈만큼 불을 4방으로 이동시킨다(맵 안에 있고, 방문한 적 없고 '.'인 경우). 방문했다고 표시하고 'F'로 바꾼다.

  3-2. 지훈의 큐 사이즈만큼 지훈을 4방으로 이동시킨다(맵 안에 있고, 방문한 적 없고 '.'인 경우). 방문했다고 표시한다.

  3-3. 지훈이를 이동시킬 때, 매번 벽에 닿았는지 확인한다. 만약 닿았다면 끝낸다.

4. 지훈의 큐가 비어서 끝난 경우 'IMPOSSIBLE' 출력하고 끝낸다. 벽에 닿아서 끝난 경우 벽 밖으로 나가는 것까지 포함해서 cnt 값에 1을 더한 답을 출력하고 끝낸다.

 

 

 

생각

테스트케이스를 모아둔 글(https://www.acmicpc.net/board/view/31494) 덕분에 불이 지훈보다 먼저 이동한다는 걸 알게 되었다. 그리고 제출했더니 90프로 이상에서 틀렸는데 가장 작은 경우의 테스트케이스(https://www.acmicpc.net/board/view/47134)를 생각하지 못했기 때문이었다.

 

 

 

코드

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 BOJ4179 {
	static int R, C;
	static char[][] map;
	static boolean[][] visited;
	static int[][] d = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

	static class Position {
		int x, y;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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]; // 방문 체크. 지훈이와 불 모두 함께 사용

		boolean canEscapeNow = false; // 시작부터 끝날 수 있는지 확인
		Queue<Position> Jihoon = new LinkedList<>(); // 지훈이 위치
		Queue<Position> fires = new LinkedList<>(); // 불 위치

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 'J') {
					if (i == 0 || i == R - 1 || j == 0 || j == C - 1) {
						canEscapeNow = true; // 시작부터 벽에 붙어있다면 즉시 탈출 가능
					}
					Jihoon.add(new Position(i, j)); // 지훈이 위치 넣기
					map[i][j] = '.'; // 지훈이 위치 .으로 바꾸기
					visited[i][j] = true; // 방문 체크
				} else if (map[i][j] == 'F') {
					fires.add(new Position(i, j)); // 불 위치 넣기
					visited[i][j] = true; // 방문 체크
				}
			}
		}

		if (canEscapeNow) { // 시작부터 탈출 가능하다면 1 출력하고 끝
			System.out.println(1);
		} else { // 그 외의 경우는 bfs로 탐색 시작하기
			System.out.println(escape(Jihoon, fires));
		}
	}

	private static String escape(Queue<Position> jihoon, Queue<Position> fires) {
		int cnt = 0;
		boolean isFinished = false;

		while (!jihoon.isEmpty()) {
			cnt++; // 시간 증가

			moveFire(fires); // 불부터 이동시키기
			isFinished = moveJihoon(jihoon); // 지훈이 이동시키기

			if (isFinished) { // true라면 탈출 성공
				return String.valueOf(cnt + 1); // 벽에서 밖으로 나가는 것 때문에 1 추가해서 리턴
			}
		}

		return "IMPOSSIBLE"; // 여기까지 오면 탈출 못했기 때문에 IMPOSSIBLE 리턴
	}

	private static void moveFire(Queue<Position> fires) { // 불 이동시키기. bfs
		int size = fires.size();

		for (int i = 0; i < size; i++) { // 불 큐 사이즈만큼 반복
			Position cur = fires.poll();

			for (int j = 0; j < 4; j++) {
				int dx = cur.x + d[j][0];
				int dy = cur.y + d[j][1];
				if (dx >= 0 && dx < R && dy >= 0 && dy < C && map[dx][dy] == '.' && !visited[dx][dy]) {
					map[dx][dy] = 'F';
					fires.add(new Position(dx, dy));
					visited[dx][dy] = true;
				}
			}
		}
	}

	private static boolean moveJihoon(Queue<Position> jihoon) { // 불 이동시키기. bfs
		int size = jihoon.size();

		for (int i = 0; i < size; i++) { // 지훈이 큐 사이즈만큼 반복
			Position cur = jihoon.poll();

			for (int j = 0; j < 4; j++) {
				int dx = cur.x + d[j][0];
				int dy = cur.y + d[j][1];
				if (dx >= 0 && dx < R && dy >= 0 && dy < C && map[dx][dy] == '.' && !visited[dx][dy]) {
					if (dx == 0 || dx == R - 1 || dy == 0 || dy == C - 1) { 
                    	// 미로의 가장자리에 접한 공간에 도달했다면
						return true; // true 리턴해서 끝내기
					} else {
						jihoon.add(new Position(dx, dy));
						visited[dx][dy] = true;
					}
				}
			}
		}
		return false; // 벽에 도착 못했다면 false 리턴
	}
}