[백준][자바][5427 불]

 맞았다 

저번에 못풀었던 문제라서 다시 도전했는데

바뀐건 다음과 같다'

일단 

1. BufferedReader,StringTokenizer 를 사용해서 입출력시간을 줄이고

2. 객체 생성하는 걸 피하고

3. 한테스트 케이스 마다 출력하고 초기화를 진행했다.

그래서.. .실패했다..

뭐지 싶었다.. 저번도 33%에서 시간초과였는데...다른문젠가..싶어서..

질문 검색을 찾아보니

"queue에 중복으로 들어가는 것을 막으셔야합니다."
라고 하더라..

생각해보니 상근이든 불이든 큐를 넣게 되면 큐의 사이즈는 계속 비대하게 쌓여간다

어떻게하면 막을수 있을까 생각해보니 그냥 단순하게 visit 배열을 만들면될거같았다

만들고 실행하니 성공했다.ㅎㅎ

메모리가 커보여서 동적으로 배열도 만드니 절반이나 메모리가 줄었다.

ㅠ 너무 놀았다...약속이 3일 연속으로 잡혀서 ㅠㅠ 

오늘도 잡힐뻔했는데 다행이도 취소됬다. 휴...공부해얒..ㅎ 

package aa;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class f_Point{
	int x;
	int y;
	f_Point(int y, int x){
		this.x = x; 
		this.y = y; 
	}
}
public class backjoon_5427_불_new {
	static int n;
	static int w;
	static int h;
	static int testCase ;
	static int cnt = 0;
	static int[][] map;
	static boolean[][] s_Visit;
	static boolean[][] f_Visit;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static Queue fire_Q;
	static Queue sangun_Q;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		testCase = Integer.parseInt(br.readLine());
		for ( int t = 0; t < testCase; t++) {

			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			
			
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			//초기화
			map = new int[h][w];
			s_Visit = new boolean[h][w];
			f_Visit = new boolean[h][w];
			fire_Q = new LinkedList();
			sangun_Q = new LinkedList();
			cnt = 0;
			//초기화 끝
			for ( int i = 0 ; i < h; i++) {
				String s = br.readLine();
				for (int j=0; j< w; j++) {
					char c = s.charAt(j);
					if ( c == '.' ) map[i][j] = 0;
					if ( c == '#' ) map[i][j] = 1;
					if ( c == '*' ) {
						map[i][j] = 2;
						fire_Q.add(new f_Point(i, j));
						f_Visit[i][j] = true;
					}
					if ( c == '@' ) {
						map[i][j] = 3;
						sangun_Q.add(new f_Point(i,j));
						s_Visit[i][j] = true;
					}
					
				}
			}
			
			while(true) {
				//print_Map();
				cnt += 1;
				fire_Move();
				if ( sangun_Move()) {
					System.out.println(cnt);
					break;
				}
				//결과가 false면 
				if(!escapePossible()) {
					System.out.println("IMPOSSIBLE");
					break;
				}
			}
		}
	
	}
	
	public static void print_Map() {
		System.out.println("----------");
		for (int i = 0; i< h; i++) {
			for (int j = 0; j < w; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("----------");
	}
	public static boolean escapePossible() {
		if( sangun_Q.isEmpty() ) {
			return false;
		}
		return true;
	}
	public static void fire_Move() {
		int fireSize = fire_Q.size() ;
		
		for ( int s = 0; s < fireSize; s++ ) {
			f_Point fp = fire_Q.poll();
			int sero = fp.y;
			int garo = fp.x;
			for (int i = 0 ; i < 4; i++) {
				int xx = dx[i] + garo;
				int yy = dy[i] + sero;
				if ( xx >= 0 && xx < w && yy >= 0 && yy < h ) {
					// 빈 공간이면 불 번지기 
					if ( map[yy][xx] != 1 && !f_Visit[yy][xx]) {
						map[yy][xx] = 2;
						f_Visit[yy][xx] = true;
						fire_Q.add(new f_Point(yy,xx));
						
					}
				}
				
			}
		}
	}
	public static boolean sangun_Move() {
		int fireSize = sangun_Q.size() ;
		for ( int s = 0; s < fireSize; s++ ) {
			f_Point fp = sangun_Q.poll();
			int sero = fp.y;
			int garo = fp.x;
			for (int i = 0 ; i < 4; i++) {
				int xx = dx[i] + garo;
				int yy = dy[i] + sero;
				//탈출 가능 일시 
				if ( xx < 0 || xx >= w || yy < 0 || yy >= h ) {
					return true;
				}
				if ( xx >= 0 && xx < w && yy >= 0 && yy < h ) {
					// 빈 공간이면 불 번지기 
					if ( map[yy][xx] == 0 && !s_Visit[yy][xx]) {
						map[yy][xx] = 3;
						s_Visit[yy][xx] = true;
						sangun_Q.add(new f_Point(yy,xx));
						
					}
				}
				
			}
		}
		return false;
	}

}