[BOJ 4179] 불!

가장 일반적인 시뮬레이션 + bfs 문제다

문제

---

(R, C) 크기의 배열에서 지훈이의 위치는 1개, 불의 위치는 1개 이상이 배열안에 있다.
1분이 지날 때 마다 지훈이와 불은 사방탐색으로 퍼진다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.
지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

배열에는 다음과 같이 주어진다.
#: 벽
.: 지나갈 수 있는 공간
J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
F: 불이 난 공간

[풀이 코드]

---

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, result;
	static boolean impossible;
	static char[][] arr;
	static int[] dr = {0, 0, 1, -1};
	static int[] dc = {1, -1, 0, 0};
	static Queue<Point> jh_queue;
	static Queue<Point> fire_queue;
	static boolean[][] jh_v;
	static boolean[][] fire_v;
	
	
	static class Point {
		int r, c, cnt;
		Point(int r, int c, int cnt) {
			this.r=r;
			this.c=c;
			this.cnt=cnt;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new char[N][M];
		jh_v = new boolean[N][M];
		fire_v = new boolean[N][M];
		jh_queue = new ArrayDeque<>();
		fire_queue = new ArrayDeque<>();
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = s.charAt(j);
				// queue에 불 위치 삽입
				if(arr[i][j]=='F') {
					fire_queue.offer(new Point(i, j, 0));
					fire_v[i][j] = true;
				}
				if(arr[i][j]=='J') {
					jh_queue.offer(new Point(i, j, 0));
					jh_v[i][j] = true;
				}
			}
		}
		result = bfs();
		if(result==-1) {
			System.out.println("IMPOSSIBLE");
		}else {
			System.out.println(result+1);
		}
	}
	private static int bfs() {
		
		while(!jh_queue.isEmpty()) {
			// 불 이동
			int fireQueueSize = fire_queue.size();
			for (int f = 0; f < fireQueueSize; f++) {
				Point fire = fire_queue.poll();
				for (int d = 0; d < 4; d++) {
					int nr = fire.r + dr[d];
					int nc = fire.c + dc[d];
					if(nr<0 || nr>=N || nc<0 || nc>=M || arr[nr][nc]=='#' || fire_v[nr][nc]) continue;
					fire_queue.offer(new Point(nr, nc, fire.cnt+1));
					fire_v[nr][nc] = true;
				}
			}			

			// 지훈 이동
			int jhQueueSize = jh_queue.size();
			for (int j = 0; j < jhQueueSize; j++) {
				Point jh = jh_queue.poll();
				if(jh.r==0 || jh.r==N-1 || jh.c==0 || jh.c==M-1) {
					return jh.cnt;
				}
				
				for (int d = 0; d < 4; d++) {
					int nr = jh.r + dr[d];
					int nc = jh.c + dc[d];
					if(nr<0 || nr>=N || nc<0 || nc>=M || arr[nr][nc]!='.' || jh_v[nr][nc] || fire_v[nr][nc]) continue;
					jh_queue.offer(new Point(nr, nc, jh.cnt+1));
					jh_v[nr][nc] = true;
				}	
			}
		}
		return -1;
	}
}

처음에는 방문배열을 하나만 사용했고, 지훈이 이동할 때 마다 배열 위치에 'J'를 넣어 상태를 갱신하는 방식으로 구현했다. 이 방식은 불과 지훈이의 상태가 섞이고, 또 매 이동마다 문자 배열에 Update가 계속 일어나서 메모리 사용량이 많아졌다. 그래서 메모리 초과가 났다.

그래서 메모리 초과를 해결하기 위해서 지훈과 불의 방문배열 2개를 사용하여 더 이상 배열에 'J'를 수정하지 않아도 되었다.