코딩테스트-알고리즘/백준 BOJ
[백준 BOJ/Gold IV] 4179번 : 불!
닉네임생각즁
2024. 3. 19. 19:56
https://www.acmicpc.net/problem/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");
}
}