[소프티어] 7726. 나무 섭지

나 무섭지

https://softeer.ai/practice/7726

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

class Pair {
    int x, y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int MAX_NM = 1000;
    public static final int INF = 987654321;

    public static int n, m, player_step;
    public static int exit_x, exit_y;
    public static Pair[] monster_list = new Pair[MAX_NM*MAX_NM];
    public static int monster_num;
    public static String[] board = new String[MAX_NM];

    public static int[][] dxdy = new int[][]{{-1, 0, 1, 0}, {0, 1, 0, -1}};
    public static boolean isRange(int x, int y) {
        return x>=0 && x<n && y>=0 && y<m;
    }

    public static Queue<Pair> que = new LinkedList<>();
    public static int[][] step = new int[MAX_NM][MAX_NM];
    
    public static void main(String[] args) {
        // 1. input
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; ++i) {
            board[i] = sc.next();
        }
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                step[i][j] = INF;
                
                if (board[i].charAt(j) == 'D') {
                    exit_x = i;
                    exit_y = j;
                }
                else if (board[i].charAt(j) == 'G') {
                    monster_list[monster_num++] = new Pair(i, j);
                }
                else if (board[i].charAt(j) == 'N') {
                    que.add(new Pair(i, j));
                    step[i][j] = 0;
                }
            }
        }

        // 2. simulation
        while (!que.isEmpty()) {
            Pair curr = que.poll();
            int x = curr.x, y = curr.y;
            int nx, ny;
            for (int dir = 0; dir < 4; ++dir) {
                nx = x + dxdy[0][dir];
                ny = y + dxdy[1][dir];

                if (isRange(nx, ny) && board[nx].charAt(ny) != '#' && step[nx][ny] > step[x][y] + 1) {
                    step[nx][ny] = step[x][y] + 1;
                    que.add(new Pair(nx, ny));
                }
            }
        }
        
        if (step[exit_x][exit_y] == INF) {
            System.out.println("No");
        }
        else {
            player_step = step[exit_x][exit_y];
            
            
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    step[i][j] = INF;
                }
            }
            for (int i = 0; i < monster_num; ++i) {
                que.add(monster_list[i]);
                step[monster_list[i].x][monster_list[i].y] = 0;
            }
            while (!que.isEmpty()) {
                Pair curr = que.poll();
                int x = curr.x, y = curr.y;
                int nx, ny;
                for (int dir = 0; dir < 4; ++dir) {
                    nx = x + dxdy[0][dir];
                    ny = y + dxdy[1][dir];
    
                    if (isRange(nx, ny) && step[nx][ny] > step[x][y] + 1) {
                        step[nx][ny] = step[x][y] + 1;
                        que.add(new Pair(nx, ny));
                    }
                }
            }

            if (step[exit_x][exit_y] <= player_step) {
                System.out.println("No");
            }
            else {
                System.out.println("Yes");
            }
        }

        
    }
}