자바(백준) 4179 불!

오답 노트 & 새로 알게 된 점

 

이런 유형의 문제를 단계별 bfs문제라고 생각한다.

한 번에 bfs를 돌려서 문제의 답을 구하는 것이 아니라, 

한 타임 돌리고, 또 한 타임 돌리면서 답을 구하는 것이다.

 

이 문제도 보면 불이 이동하고 -> 지훈이가 이동한다.  이게 한 사이클이다.

 

문제에서 동시에 이동한다고 했으니, 불이 먼저 이동할까 지훈이가 먼저 이동할까를 생각해봤다.

 

동시에 이동한다고 했을 때, 불이 있는 곳에 지훈이가 가면 어떻게 될까 라는 생각을 했고,

이로 인해 불이 먼저 움직여야겠다는 결론을 내렸다.

 

불이 이동하는 bfs, 지훈이가 이동하는 bfs를 따로 만들어줬다.

 

둘의 bfs에는 공통점이 있다.

각각의 큐가 empty 될 때까지 돌리는 것이 아니라, 한 사이클만 돌린다.

즉, 현재 시점에서 들어있는 큐의 size만큼 bfs를 돌리는 것이다.

왜냐하면 1초마다 불과 지훈이가 동시에 움직이기 때문이다.

 

그래서 현재의 큐의 사이즈를 구한 다음에 size만큼 반복문을 돌려주면 된다.

 

지훈이가 이동하는 bfs는 돌릴 때마다 불을 움직여줘야한다.

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int row, col;
    static char A[][];
    static Queue<Info> fireQ = new ArrayDeque<>();
    static Queue<Info> jQ = new ArrayDeque<>();
    static boolean fireVisit[][];
    static boolean jVisit[][];
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    static int ans;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        movebfs();
 
        if(ans > 0) System.out.println(ans);
        else System.out.println("IMPOSSIBLE");
    }
 
    static void movebfs() {
 
        while (!jQ.isEmpty()) {
            moveFire();
            int size = jQ.size();
 
            for (int i = 0; i < size; i++) {
                Info info = jQ.poll();
 
                if(info.x == 0 || info.x == row - 1 || info.y == 0 || info.y == col - 1){
                    ans = info.cnt + 1;
                    return;
                }
 
                for (int j = 0; j < 4; j++) {
                    int X = info.x + dx[j];
                    int Y = info.y + dy[j];
 
                    if(!isRangeTrue(X, Y)) continue;
                    if(jVisit[X][Y]) continue;
                    if(A[X][Y] == 'F' || A[X][Y] == '#') continue;
 
                    jQ.offer(new Info(X, Y, info.cnt + 1));
                    jVisit[X][Y] = true;
                }
            }
        }
    }
 
    static void moveFire() {
 
        int size = fireQ.size();
 
        for (int i = 0; i < size; i++) {
            Info info = fireQ.poll();
 
            for (int j = 0; j < 4; j++) {
                int X = info.x + dx[j];
                int Y = info.y + dy[j];
 
                if(!isRangeTrue(X, Y)) continue;
                if(fireVisit[X][Y]) continue;
                if(A[X][Y] == '#') continue;
 
                fireQ.offer(new Info(X, Y, 0));
                fireVisit[X][Y] = true;
                A[X][Y] = 'F';
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
 
        A = new char[row][col];
 
        fireVisit = new boolean[row][col];
        jVisit = new boolean[row][col];
 
        for (int i = 0; i < row; i++) {
            String str = br.readLine();
            for (int j = 0; j < col; j++) {
                A[i][j] = str.charAt(j);
                if(A[i][j] == 'J'){
                    jQ.offer(new Info(i, j, 0));
                    jVisit[i][j] = true;
                }
                if(A[i][j] == 'F'){
                    fireQ.offer(new Info(i, j, 0));
                    fireVisit[i][j] = true;
                }
            }
        }
    }
    static class Info{
        int x, y, cnt;
 
        public Info(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}