(코테) 백준_4179_불! bfs

 

 

 

 

 

정답 

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

public class Main {
	static char[][] map ;	
	static int r ;
	static int c ;
	static int[] x = {-1,1,0,0} ;
	static int[] y = {0,0,-1,1} ;	
	static int[][] firedTime ;
	static int[][] humanTime ;
	
	public static void main(String[] args)  throws Exception {
		// TODO Auto-generated method stub
		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];   // 맵값 초기 선언.
		firedTime = new int[r][c];
		humanTime = new int[r][c];
		Queue<int[]> fireQue = new LinkedList<>();
		Queue<int[]> humanQue = new LinkedList<>();
		
		for(int i = 0; i<r;i++) {
			  map[i] = br.readLine().toCharArray();
			for(int j = 0;j <c ;j++) {
				firedTime[i][j] = -1;
				humanTime[i][j] = -1;
				if (map[i][j] == 'J') {
				    humanTime[i][j] = 0;
				    humanQue.offer(new int[]{i, j});
				}
				if (map[i][j] == 'F') {
				    firedTime[i][j] = 0;
				    fireQue.offer(new int[]{i, j});
				}		
			}
		}
		
		while(!fireQue.isEmpty()) {
			int[] current = fireQue.poll();
			int nowX = current[0];
			int nowY = current[1];

			for(int i =0; i<4;i++) {
				int nextX = current[0] +x[i];
				int nextY = current[1] +y[i];
				if(nextX < 0 || nextX >= r || nextY <0 || nextY >= c ) continue;
				if(map[nextX][nextY]=='#' || firedTime[nextX][nextY] != -1) continue;								
				firedTime[nextX][nextY] = firedTime[nowX][nowY] +1;
				fireQue.offer(new int[] {nextX,nextY});
			}
		}
				
		while(!humanQue.isEmpty()) {
			int[] current = humanQue.poll();
			int nowX = current[0];
			int nowY = current[1];
			//가장자리면 탈출
			if(nowX==0 || nowX==r-1 ||  nowY==0 || nowY == c-1){
				System.out.print(humanTime[nowX][nowY]+1);			
					return;
			}  
				
			for(int i=0; i<4;i++) {
				int nextX = current[0] + x[i];
				int nextY = current[1] + y[i];
				if(nextX < 0 || nextX >= r || nextY <0 || nextY >= c ) continue; // 4각형 벗어나는지 
				if(map[nextX][nextY]=='#' || humanTime[nextX][nextY] != -1) continue; //처음 맞는지 + 벽 아닌지
				//이미 불들어오거나 동시에 들어올 에정인지
				if(firedTime[nextX][nextY] != -1 && humanTime[nowX][nowY] +1 >= firedTime[nextX][nextY] ) continue;
//				if (firedTime[nextX][nextY] != -1 && firedTime[nextX][nextY] <= humanTime[nowX][nowY] + 1) continue;

				
					humanTime[nextX][nextY] = humanTime[nowX][nowY] +1;
					humanQue.offer(new int[] {nextX,nextY});			
			}
			
			
		}
		
		
		System.out.print("IMPOSSIBLE");
	
		
	}

	

}

 

 

회고

1. 큐를 두개로 나눌 생각을 못함.

2. 점화 시간 , 사람 시간을 2개 이중 배열로 나눠 시간을 측정할 생각을 못함. 

3.점화시간을 먼저 선행 작업하고  사람 while 문에서 이제 시뮬레이션 하는게 창의적이였음.