[백준 BOJ/Gold IV] 4179번 : 불!

 

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

4179번: 불!

 

 

 

현재 각 큐에 담겨있는만큼 꺼내서 상하좌우를 체크해주는데 

처음에는 지훈이 이동 체크 -> 불 이동 체크 순서로 진행하며 다음으로 넘어갔다

예제는 통과했지만 채점을 하다가 틀렸다고 나오는거다😐😐

 

반례를 여러가지 찾아서 넣어보다가

3 4
##.#
FJ.#
##F#

ans : IMPOSSIBLE

 

이거를 넣어보고 왜 틀렸는지 알게되었다

F가 두개 이상 동시에 퍼질때 지훈이가 이동할 수 있는 곳을 먼저 체크하게 되면 다른 방향에서 번지는 불을 체크하지 못하고 이동할 수 있다고 판단하는 경우가 생기게 되는 것이다

bfs 안에서 불이 퍼지는것을 먼저 확인하고 지훈이가 움직히는것을 확인하니 정답이 되었다!!!!!

순서도 굉장히 중요하니 꼼꼼하게 잘 살펴보자👊👊

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int R;
	static int C;
	static String[][] maze;
	static Deque<int[]> hoon;
	static Deque<int[]> fire;
	
	static int count = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		R = Integer.parseInt(str[0]);
		C = Integer.parseInt(str[1]);
		maze = new String[R][C];
		hoon = new ArrayDeque<>();
		fire = new ArrayDeque<>();
		
		for (int i = 0; i < R; i++) {
			str = br.readLine().split("");
			for (int j = 0; j < C; j++) {
				maze[i][j] = str[j];
				if (maze[i][j].equals("J")) hoon.addLast(new int[] {i, j});
				else if (maze[i][j].equals("F")) fire.addLast(new int[] {i, j});
			}
		}
				
		bfs();
		
	}
	
	static void bfs() {
				
		while (!hoon.isEmpty()) {
			
			int fireSize = fire.size();
			for (int i = 0; i < fireSize; i++) {
				
				int[] xy = fire.pollFirst();
				int x = xy[0];
				int y = xy[1];
				
				for (int j = 0; j < 4; j++) {
					int nx = x + dx[j];
					int ny = y + dy[j];
					
					if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
						if (!maze[nx][ny].equals("#") && !maze[nx][ny].equals("F")) {
							fire.addLast(new int[] {nx, ny});
							maze[nx][ny] = "F";
						}
					}
				}
			}
			
			int hoonSize = hoon.size();
			for (int i = 0; i < hoonSize; i++) {
				
				int[] xy = hoon.pollFirst();
				int x = xy[0];
				int y = xy[1];
				
				if (x == 0 || x == R-1 || y == 0 || y == C-1) {
					System.out.println(count + 1);
					return;
				}
				
				for (int j = 0; j < 4; j++) {
					int nx = x + dx[j];
					int ny = y + dy[j];
					
					if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
						if (maze[nx][ny].equals(".")) {
							hoon.addLast(new int[] {nx, ny});
							maze[nx][ny] = "J";
						}
					}
				}
			}
					
			count++;
			
		}
		
		System.out.println("IMPOSSIBLE");		
	}

}