[백준 / JAVA] 4179. 불!

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

4179번: 불!

 

---

💻 풀이 결과

 

💯 최종 코드

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

class Node {
	int r, c;

	Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

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

		Queue<Node> fire = new LinkedList<>();
		Queue<Node> jihoon = new LinkedList<>();
		boolean[][] visited = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			String str = sc.next();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);

				if (map[i][j] == 'F') {
					fire.add(new Node(i, j));
				}
				if (map[i][j] == 'J') {
					jihoon.add(new Node(i, j));
					visited[i][j] = true;
				}
			}
		}

		int cnt = 0;
		int[] dr = { 0, 0, -1, 1 };
		int[] dc = { -1, 1, 0, 0 };
		boolean isPossible = false;

		// 지훈이가 가장자리로 갈 때까지
		while (!jihoon.isEmpty()) {
			// 매분마다 불이 확산된다.
			int fireSize = fire.size();

			for (int fs = 0; fs < fireSize; fs++) {
				Node curr = fire.poll();

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

					if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
						continue;
					}

					// 불이 퍼진 지점을 큐에 삽입
					if (map[nr][nc] == '.') {
						fire.add(new Node(nr, nc));
						// 불 났다고 표시
						map[nr][nc] = 'F';
					}
				}
			} // 불 퍼지는 것 끝

			int size = jihoon.size();
			cnt++;

			for (int s = 0; s < size; s++) {
				Node curr = jihoon.poll();

				// 종료 조건
				if (curr.r == 0 || curr.r == R - 1 || curr.c == 0 || curr.c == C - 1) {
					isPossible = true;
					jihoon.clear();
					break;
				}

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

					if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
						continue;
					}
					if (visited[nr][nc]) {
						continue;
					}

					// 이동할 수 있는 지점을 큐에 삽입
					if (map[nr][nc] == '.') {
						jihoon.add(new Node(nr, nc));
						visited[nr][nc] = true;
						map[curr.r][curr.c] = '.';
					}
				}
			}
		}

		if (isPossible) {
			System.out.println(cnt);
		} else {
			System.out.println("IMPOSSIBLE");
		}
	}
}

 

💢 틀린 이유

1. 메모리 초과

• 지훈이의 위치 노드를 담는 큐에서 메모리 초과가 발생한 것을 발견하였다.
• 메모리 초과가 발생한 이유는 지훈이 위치를 큐에 담을 때 방문처리를 하지 않아서 계속해서 다음 갈 수 있는 위치들이 큐에 담기는 로직이었기 때문이다.
• visited 배열을 만들어 지훈이 위치에 대해 방문 처리를 해줘서 해결하였다.

2. 불의 확산 vs 지훈이의 이동

• 처음 구현한 로직은 불의 확산과 지훈이의 이동의 순서를 고려하지 않았다.
• 생각해 보니 사건은 동시에 일어나기 때문에, 불을 먼저 확산시키고 불이 퍼진 자리는 지훈이가 이동하지 못하도록 처리하였다.

💬 풀이 과정

• BFS 큰 틀은 지훈이 위치에 대한 큐가 비었을 때 종료하도록 하였다.
• 불이 난 자리들의 위치와 지훈이의 위치를 각각 큐에 삽입한 채로 시작하였다.
• 1초 단위로 일어나는 일들을 순서대로 구현한다는 생각으로, 불들을 확산시키고 지훈이를 이동시켰다.
• 4방 탐색을 통해 불을 확산시키고 불이 퍼진 자리를 처리하였다.
• 불이 한번 퍼질 때마다 지훈이를 한번 이동시키고 방문처리하였다.
• 지훈이 위치를 꺼냈을 때 탈출할 수 있는 지점이라면 큐를 비워 즉시 종료되도록 하였다.

💡 깨달은 점

1. BFS 응용 - 시작점이 두 종류일 때

• 두 시작점에 대한 각각의 BFS를 돌린다.
• 두 BFS에 대한 처리 순서를 신경 써야 한다.
• 두 BFS가 서로 영향을 주는 문제의 경우에는 이러한 로직으로 풀 수가 없다. 그래서 시간 순으로 동시에 진행시켜야 한다. (백트래킹 기법 사용 필요)