[JAVA] 백준 4179 불!

1) 문제

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

2) 접근 방법

문제를 보면서 지훈이랑 불이랑 둘 다 각각 BFS 돌려서 풀어야겠다고 생각했지만..
가장 빠른 탈출시간 을 어떻게 구할지에 대한 고민이 컸다.

일단 불 먼저 BFS 돌려서 어느 위치에 몇 단위시간 만에 도착인지를 표시했다.
그 후 지훈이를 BFS 돌려서 어느 위치에 몇 단위시간 만에 도착인지 표시했는데,,
처음에는 일단 탈출 가능한 위치들을 ArrayList에 담아서..
그 ArrayList 중 탈출 조건에 맞는 걸 찾는 방식으로.. 풀었더니만 메모리랑 시간이 너무 크게 나왔다..

그래서 다른 분의 코드를 보며 살짝 수정해보았다.

출처 : https://dongho-dev.tistory.com/31

가장 빠른 탈출시간은, BFS를 돌리면서 배열의 범위를 벗어난 그 즉시! 탈출이라고 하면 된다.
그게 가장 빠르게 탈출한 시간이다!!
이렇게 진행했더니

조금이나마 줄어들게 되었다..

이 문제가 너무 예제가 조금 나와있어서 반례 찾기가 어려웠는데
(하 반례 스스로 생각해내는 경지까지 도달하고 싶지만.. 일단은.. 구현부터 잘 하는걸로..)
아래 글 작성자분들 덕분에 많은 도움을 받았습니다.. 감사합니다!

반례 참고 :
https://www.acmicpc.net/board/view/130585
https://www.acmicpc.net/board/view/126283

3) 코드

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

public class Main {

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        char[][] map = new char[r][c];
        Queue<Node> jq = new LinkedList<>();
        Queue<Node> fq = new LinkedList<>();
        int[][] jVisited = new int[r][c];
        int[][] fVisited = new int[r][c];
        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'J') {
                    jq.offer(new Node(i, j));
                    jVisited[i][j] = 1;
                } else if (map[i][j] == 'F') {
                    fq.offer(new Node(i, j));
                    fVisited[i][j] = 1;
                }
            }
        }

        // 불
        while (!fq.isEmpty()) {

            Node fNow = fq.poll();
            int fx = fNow.x;
            int fy = fNow.y;

            for (int i = 0; i < 4; i++) {
                int nx = fx + dx[i];
                int ny = fy + dy[i];

                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if (map[nx][ny] != '#' && fVisited[nx][ny] == 0) {
                    fq.offer(new Node(nx, ny));
                    fVisited[nx][ny] = fVisited[fx][fy] + 1;
                }
            }
        }

        // 지훈
        while (!jq.isEmpty()) {

            Node now = jq.poll();
            int jx = now.x;
            int jy = now.y;

            for (int i = 0; i < 4; i++) {
                int nx = jx + dx[i];
                int ny = jy + dy[i];

                if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
                    System.out.println(jVisited[jx][jy]);
                    return;
                }
                if (fVisited[nx][ny] != 0 && fVisited[nx][ny] <= jVisited[jx][jy] + 1) continue;
                if (map[nx][ny] != '#' && jVisited[nx][ny] == 0) {
                    jq.offer(new Node(nx, ny));
                    jVisited[nx][ny] = jVisited[jx][jy] + 1;
                }
            }
        }

        System.out.println("IMPOSSIBLE");
    }
}

class Node {
    int x;
    int y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}