나무 섭지

풀고서도

이렇게 단순한 풀이가 맞다고??? 라고 놀란 문제..

 

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

public class Main {
    static int n, m ,namwuX,namwuY, goalX, goalY, minGhostLen=Integer.MAX_VALUE;
    static char[][] map;
    static List<int[]> ghosts = new ArrayList<>();
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) {
        init();

        if(exit() < minGhostLen) System.out.println("Yes");
        else System.out.println("No");
    }

    public static int exit() {
        int[][] dp = new int[n][m];
        for(int i=0; i<n; i++) Arrays.fill(dp[i], n*m+1);
        
        Queue<int[]> q = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        q.add(new int[] {namwuX, namwuY, 0});
        dp[namwuX][namwuY] = 0;
        
        while(!q.isEmpty()) {
            int[] p = q.poll();

            if(p[0] == goalX && p[1] == goalY) {
                return p[2];
            }

            for(int d=0; d<4; d++) {
                int nx = p[0] + dx[d];
                int ny = p[1] + dy[d];

                if(inMap(nx, ny) && map[nx][ny] != '#' && dp[nx][ny] > p[2] + 1) {
                    dp[nx][ny] = p[2] + 1;
                    q.add(new int[] {nx, ny, p[2]+1});
                }
            }
        }
        ///////
        return Integer.MAX_VALUE;
    }

    public static void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new char[n][m];

        for(int i=0; i<n; i++) {
            String s = sc.next();
            for(int j=0; j<m; j++) {
                if('N' == s.charAt(j)) {
                    namwuX = i;
                    namwuY = j;
                    map[i][j] = '.';
                }
                else if('G' == s.charAt(j)) {
                    ghosts.add(new int[] {i, j, 0});
                    map[i][j] = '.';
                }
                else {
                    if('D' == s.charAt(j)) {
                        goalX = i;
                        goalY = j;
                    }
                    map[i][j] = s.charAt(j);
                }
            }
        }


        
        for(int i=0; i<ghosts.size(); i++) {
            int len = Math.abs(goalX - ghosts.get(i)[0]) + Math.abs(goalY - ghosts.get(i)[1]);
            ghosts.get(i)[2] = len;
        }

        if(ghosts.size() > 0) {
            Collections.sort(ghosts, (a,b) -> a[2] - b[2]);
            minGhostLen = ghosts.get(0)[2];
        }
        ///
    }

    public static boolean inMap(int x, int y) {
        if(x>=0&&x<n && y>=0&&y<m) return true;
        return false;
    }
}

 

 

고스트가 먼저 골에 도착하면, 남우는 통과하지 못한다.

라는 아이디어밖에 떠오르지 않아서, 일단 그거부터 구현해야지~~~ 했다가 그게 정답의 전부였다는....

 

블로그 보니까 이런 풀이가 맞는 거 같다.

그런데 유령을 bfs 돌리는 코드가 있던데,

유령은 문제에서 주어진 거처럼 벽도 통과한다. 굳이 bfs를 돌리지 않고, x좌표차이 + y좌표차이 하면 더 빠르게 구할 수 있다.