[Java/BFS] 소프티어. 나무섭지

🤔 Intuition

BFS를 이용한 완탐으로 보였다.

귀신이 남우를 따라잡는 여부를 어떻게 알 수 있나 기준을 잡는 게 중요했는데, 귀신이 남우보다 먼저 목적지에 갈 수 있는 경우에는 무조건 귀신이 남우를 따라잡을 수 있는 것으로 봤다.

 

여기서 고민을 했던 부분은 최악의 경우 10^6 개의 귀신을 가질 텐데, 이들이 모두 BFS를 돌면 시간을 쉬이 초과할 것이다. 따라서 탐색을 할 귀신을 선정하는 게 중요한데, 나는 도착지와 맨해튼 거리가 가장 가까운 귀신만 검사해줬다. 어차피 가장 가까운 귀신의 이동 거리만 필요하기 때문이다.

 

(솔직히 처음에 제출할 때에는, "에이 그래도 이게 뻑이 안나도록 문제를 줬을거야 누가봐도 BFS 문제인데?" 라는 아주아주 안일한 생각을 했다. 결론은, 문제에서 단순 완탐이 아니라 필요한 경우만 탐색하도록 로직을 구성하게끔 의도하고 있었다. 레슨런으로는, "이 로직이 맞는거같은데 아주아주 최악의 경우에는 TLE가 발생하네? 하지만 그렇게 TC를 구성하진 않았을거야" 라는 안일한 생각은 절대 금물이고, 반드시 철저하게 시간에 들어오도록 로직을 구성해야 한다.)

🔎 Algorithm & Complexity

* @algorithm bfs
* @time O(N*M) : 남우와 고스트 1개의 출발점부터 bfs 탐색 1번씩
* @memory O(N*M)

👨🏻‍💻 Logic

1. 배열을 입력받는다. 이 과정에서 귀신 좌표들과 도착지점, 남우 좌표를 저장해 두는게 필요하다.
2. 남우의 이동거리는 적절한 INF 값으로 초기화해둔다. (나중에 이를 이용하여 남우가 벽에 막혔는지 검사한다.)
3. 귀신들의 좌표를 순회하면서 destination과 가장 맨해튼 거리가 가까운 좌표만 ghostY, ghostX로 저장한다.
4. bfs를 남우 좌표, 귀신 좌표로 돌려서 귀신이 목적지까지 이동한 거리, 남우가 목적지까지 이동한 거리를 저장한다.
5. 남우가 이동한 거리가 귀신보다 빠르면 Yes, 느리면 No를 출력한다. 이 때, 남우가 만약 벽에 막혀서 목적지에 도달하지 못하는 경우에도 목적지 좌표에 저장된 남우의 이동거리가 INF로 설정되어 있어서 자동으로 No 처리가 된다.

public class SFT_나무섭지 {
    private static int N, M;
    private static int[][] map; // '.' : 0, 'D' : 1, '#' : 2, 'G' : 3, 'N' : 9
    private static final int EMPTY = 0;
    private static final int DEST = 1;
    private static final int WALL = 2;
    private static final int GHOST = 3;
    private static int nwY, nwX, destY, destX, ghostY, ghostX;
    private static int[][] gStep;
    private static int[][] nStep;
    private static boolean[][] visited;
    private static int[] dy = {1, -1, 0, 0};
    private static int[] dx = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        gStep = new int[N][M];
        nStep = new int[N][M];

        List<int[]> ghosts = new ArrayList<>();
        // 맵 입력
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                String ss = s.substring(j, j + 1);
                // "." 비어있는 경우는 어차피 0으로 기록할 거라서 처리할 필요 없음
                 if (ss.equals("D")) {
                    map[i][j] = DEST;
                    destY = i;
                    destX = j;
                } else if (ss.equals("#")) {
                    map[i][j] = WALL;
                } else if (ss.equals("G")) {
                    map[i][j] = GHOST;
                    ghosts.add(new int[]{i, j});
                } else if (ss.equals("N")) {
                    // 남우가 움직일 때 장애물 여부를 판단하려고 맵을 보는 거니까 맵에 반영할 필요 없음
                    nwY = i;
                    nwX = j;
                }

                 nStep[i][j] = (int) 1e9;
                 gStep[i][j] = (int) 1e9;
            }
        }

        ghostY = (int) 1e9;
        ghostX = (int) 1e9;
        for (int[] ghost : ghosts) {
            int y = ghost[0];
            int x = ghost[1];
            int newDist = Math.abs(y - destY) + Math.abs(x - destX);
            int originDist = Math.abs(ghostY - destY) + Math.abs(ghostX - destX);
            if (originDist > newDist) {
                ghostY = y;
                ghostX = x;
            }
        }

        bfs(nwY, nwX, true);
        // 귀신은 dest와 맨해튼 거리가 가장 가까운 놈만 하자.
        bfs(ghostY, ghostX, false);

        br.close();
        bw.write(sb.append(nStep[destY][destX] < gStep[destY][destX] ? "Yes" : "No").toString());
        bw.flush();
        bw.close();
    }

    private static void bfs(int startY, int startX, boolean isHuman) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{startY, startX});
        visited = new boolean[N][M];
        visited[startY][startX] = true;
        if (isHuman) {
            nStep[startY][startX] = 0;
        } else {
            gStep[startY][startX] = 0;
        }

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int y = now[0];
            int x = now[1];

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (isHuman ? canGo(ny, nx) : canGhost(ny, nx)) {
                    if (isHuman) {
                        nStep[ny][nx] = Math.min(nStep[ny][nx], nStep[y][x] + 1);
                    } else {
                        gStep[ny][nx] = Math.min(gStep[ny][nx], gStep[y][x] + 1);
                    }
                    if (ny == destY && nx == destX) {
                        return;
                    }
                    visited[ny][nx] = true;
                    q.add(new int[]{ny, nx});
                }
            }
        }
    }

    private static boolean canGhost(int y, int x) {
        return inRange(y, x) && !visited[y][x];
    }
    private static boolean canGo(int y, int x) {
        return inRange(y, x) && map[y][x] <= 1 && !visited[y][x];
    }
    private static boolean inRange(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < M;
    }
}