[소프티어] 나무 섭지(JAVA)

문제

https://softeer.ai/practice/7726

---

풀이(20분)

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

public class Main {
    static int n, m;
    static int[][] ghost;
    static char[][] map;
    static int[][] man;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        ghost = new int[n][m];
        map = new char[n][m];
        man = new int[n][m];

        for (int i = 0; i < n; i++) {
            Arrays.fill(ghost[i], Integer.MAX_VALUE);
            Arrays.fill(man[i], -1);  // 방문 여부를 -1로 초기화
        }

        Queue<Point> ghostQueue = new LinkedList<>();
        Queue<Point> manQueue = new LinkedList<>();

        Point start = null, end = null;

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'G') {
                    ghostQueue.add(new Point(i, j, 0));
                    ghost[i][j] = 0;
                } else if (map[i][j] == 'N') {
                    start = new Point(i, j, 0);
                } else if (map[i][j] == 'D') {
                    end = new Point(i, j, 0);
                }
            }
        }

        ghostBfs(ghostQueue);
        manQueue.add(start);
        boolean canEscape = bfs(manQueue, end);

        System.out.println(canEscape ? "Yes" : "No");
    }

    public static void ghostBfs(Queue<Point> queue) {
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            int curRow = cur.row, curCol = cur.col;
            for (int i = 0; i < 4; i++) {
                int nextRow = curRow + dx[i];
                int nextCol = curCol + dy[i];
                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m) {
                    if (ghost[nextRow][nextCol] > cur.time + 1) {
                        ghost[nextRow][nextCol] = cur.time + 1;  // 방문 시간 업데이트
                        queue.add(new Point(nextRow, nextCol, cur.time + 1));
                    }
                }
            }
        }
    }

    public static boolean bfs(Queue<Point> queue, Point end) {
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            int curRow = cur.row, curCol = cur.col;

            if (curRow == end.row && curCol == end.col) {
                return true; // 출구 도착
            }

            for (int i = 0; i < 4; i++) {
                int nextRow = curRow + dx[i];
                int nextCol = curCol + dy[i];

                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m) {
                    if (man[nextRow][nextCol] == -1 && map[nextRow][nextCol] != '#') {
                        if (ghost[nextRow][nextCol] > cur.time + 1) {
                            man[nextRow][nextCol] = cur.time + 1;  // 방문 체크
                            queue.add(new Point(nextRow, nextCol, cur.time + 1));
                        }
                    }
                }
            }
        }
        return false;  // 출구 도달 실패
    }

    static class Point {
        int row, col, time;
        public Point(int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }
    }
}

---

문제 풀이 전략

 

간단하게 bfs를 하는 것이 아닌 특정한 조건(유령)을 생각해 주면 되는 문제이다.

일단, 유령은 벽에 상관없이 이동할 수 있고, 한 자리에 머물러도 된다.

-> 유령은 최단거리로 이동한 순간부터 끝까지 그 위치에 존재할 수 있다.

 

그렇기에 유령을 먼저 bfs를 해준다. 이를 통해 유령의 최단 시간 도착 및 이후 유지 상태를 관리해 준다.

 

다음으로 사람을 bfs 해준다.

사람의 경우 여러 가지 조건을 통과해야 한다.

1. 격자 안에 위치하는가

2. 방문한 적이 없는 곳인가

3. 벽이 아닌가

4. 귀신보다 더 빠르게 도달할 수 있는가

 

위의 과정을 모두 만족한다면 큐에 추가해 주고, 최단 시간으로 방문하는 기록을 체크해 준다.

 

최종적으로 끝에 도달할 수 있다면 Yse를 아니라면 No를 출력한다.