5427_불 ******** => 시간초과

메모리 초과 ->> visit 배열로 해결

시간 초과 ->>헐?

두 가지 타파법

1. 게임 시작 전에 bfs 돌면서, 각 빈 칸에 몇 초 후에 불이 붙는지 미리 저장해두고, 사람만 움직인다

2. queue에 발화점을 저장해 둔다. (한 번 발화를 한 곳은 그 다음부터 옆으로 더 번질 위험이 없으므로 빼고, 새로운 발화점을 추가한다)

 

시간초 과가 난 코드

package afterMiracom_0618;

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class Main_bj_5427_불 {

	static int w, h, time; //너비, 높이
	static char[][] startMap;
	
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		
		for (int test = 0; test < t; test++) {
			time = -1;
			
			w = sc.nextInt();
			h = sc.nextInt();
			
			Point sanggeun = null; //상근이 위치
			
			startMap = new char[h][w];
			for (int i = 0; i < h; i++) {
				String s = sc.next();
				for (int j = 0; j < w; j++) {
					// #': 벽, '@': 상근, '*': 불
					startMap[i][j] = s.charAt(j);
					if (startMap[i][j] == '@') {
						sanggeun = new Point(i, j);
						startMap[i][j] = '.';
					}
				}
			}
			//입력 끝
			
			bfs_5427(sanggeun);
			
			if(time == -1) System.out.println("IMPOSSIBLE");
			else System.out.println(time);
		} //테스트 케이스 끝
	}

	private static void bfs_5427(Point sanggeun) {
		Queue<Escape> q = new ArrayDeque<>();
		
		boolean[][] visit = new boolean[h][w];
		visit[sanggeun.x][sanggeun.y] = true;
		
		q.add(new Escape(sanggeun, 0, visit, startMap));
		
		while (!q.isEmpty()) {
			Escape escape = q.poll();
			
			char[][] map = copyMap(escape.map);
			boolean[][] flashPoint = checkFlashPoint(escape.map);
			
			//불이 번진다 , map 갱신
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if(flashPoint[i][j]) { //발화점이면, 4방 탐색으로 불 번지기
						burning(i, j, map); // map이 갱신이 되나
					}
				}
			}
			
			
			//상근이가 움직인다 => 추가. 1초 후에 번질 곳이면 못 간다, 범위 벗어나면 끝이다
			for (int d2 = 0; d2 < 4; d2++) {
				int nx = escape.sanggeun.x + dx[d2];
				int ny = escape.sanggeun.y + dy[d2];
				
				//메모리 초과 방지
				if(escape.move > w*h) return;
				
				if(nx<0 || ny<0 || nx>=h || ny>= w) { //탈출!
					time = escape.move + 1;
					return;
				}
				else {
					if(map[nx][ny] == '.') { //갈 수 있는 곳이면, 1초 후에 불이 번지는지 확인

						if( isNormalOneSecondLater(nx, ny, map) && !escape.visit[nx][ny]) {
							escape.visit[nx][ny] = true;
							q.add(new Escape(new Point(nx, ny), escape.move+1, escape.visit, map));
						}
					}
				}
			}
			
		}
	}

	private static boolean[][] checkFlashPoint(char[][] map) { //****
		boolean[][] flashPoint = new boolean[h][w]; //발화점을 표시하는 map... 불 번질 때 , 옮겨붙은 곳에서 다시 불이 움직이면 안 되니까
		
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if(map[i][j] == '*') flashPoint[i][j] = true;
			}
		}
		return flashPoint;
	}

	private static boolean isNormalOneSecondLater(int x, int y, char[][] map) {
//		for (int d = 0; d < 4; d++) {
//			int nx = x + dx[d];
//			int ny = y + dy[d];
//			
//			if(nx>=0 && ny>=0 && nx<h && ny<w && map[nx][ny] == '*') return false;
//		}
		return true;
	}

	private static void burning(int x, int y, char[][] map) {
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(nx>=0 && ny>=0 && nx<h && ny<w && map[nx][ny] == '.') { //빈 칸이거나, 사람 있는 곳이면 불 번지기
				map[nx][ny] = '*';
			}
		}
		
	}

	private static char[][] copyMap(char[][] map) {
		char[][] newMap = new char[h][w];
		
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				newMap[i][j] = map[i][j];
			}
		}
		return newMap;
	}

}

class Escape {
	Point sanggeun;
	int move;
	boolean[][] visit;
	char[][] map;
	public Escape(Point sanggeun, int move, boolean[][] visit, char[][] map) {
		super();
		this.sanggeun = sanggeun;
		this.move = move;
		this.visit = visit;
		this.map = map;
	}
	
	
}