소프티어 - 나무 섭지 (Java)

0. 개요

BFS 문제입니다.

두 번의 BFS를 통해 이 문제를 해결할 수 있습니다.

1. 유령이 시간 내에 갈 수 있는 위치
2. 남우 탈출 

https://softeer.ai/practice/7726

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

1. 유령이 시간 내에 갈 수 있는 위치

각 유령의 초기 위치를 큐에 저장해서, 각 위치에 얼마만에 유령이 도달할 수 있는지 저장해야 합니다.

 

문제의 1번 테스트 케이스를 그림으로 표현하면 아래와 같습니다.

 

유령의 거리 배열을 저장하게 된다면 아래 그림처럼 나타낼 수 있습니다.

 

유령은 벽을 통과할 수 있다는 점을 조심해야 합니다.

 

2. 남우 탈출

유령의 거리 배열을 구했으니, 남우를 탈출시키면 됩니다.

남우를 탈출 할 때 벽인지, 유령보다 빠르게 특정 위치에 갈 수 있는지 고려하면 됩니다.

 

주의해야할 점은 탈출과 동시에 유령을 만나면 안된다는 점입니다.

 

유령 거리 배열에서 (0, 5)를 보시면 6으로 저장되어 있습니다.

즉, 6턴 만에 남우가 해당 위치로 도착하더라도 탈락해야 합니다.

 

[구현 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final int[] DX = {-1, 1, 0, 0};
    private static final int[] DY = {0, 0, -1, 1};
    private static final int MAX = 987_654_321;

    private static char[][] map;
    private static Point nam, destination;

    private static int n, m;

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

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        map = new char[n][m];
        int[][] ghostDis = new int[n][m]; // 유령 거리 배열
        Queue<Point> qu = new LinkedList<>();
        for(int i=0; i<n; i++){
            Arrays.fill(ghostDis[i], MAX);
        }

        for(int i=0; i<n; i++){
            char[] chrs = br.readLine().toCharArray();
            for(int j=0; j<m; j++){
                map[i][j] = chrs[j];

                if(map[i][j] == 'G'){ // 유령 위치 저장
                    qu.add(new Point(i, j));
                    ghostDis[i][j] = 0;
                }else if(map[i][j] == 'N'){
                    nam = new Point(i, j);
                }else if(map[i][j] == 'D'){
                    destination = new Point(i, j);
                }
            }
        }

        ghostDis(qu, ghostDis);
        System.out.print(nam(ghostDis));

        br.close();
    }

    private static String nam(int[][] ghostDis) {
        Queue<Point> qu = new LinkedList<>();
        int[][] dis = new int[n][m];

        qu.add(nam);
        for(int i=0; i<n; i++){
            Arrays.fill(dis[i], MAX);
        }
        dis[nam.x][nam.y] = 0;

        while (!qu.isEmpty()){
            Point cn = qu.poll();

            if(cn.x == destination.x && cn.y == destination.y){
                return "Yes";
            }

            for(int d = 0; d<DX.length; d++){
                int nx = cn.x + DX[d];
                int ny = cn.y + DY[d];

                if(isOutOfRange(nx, ny) ||
                        map[nx][ny] == '#' ||
                        ghostDis[nx][ny] <= dis[cn.x][cn.y] + 1 ||
                        dis[nx][ny] <= dis[cn.x][cn.y] +1) continue;

                dis[nx][ny] = dis[cn.x][cn.y] + 1;
                qu.add(new Point(nx, ny));
            }
        }

        return "No";
    }

    // 유령이 각 시간마다 갈 수 있는 위치
    private static void ghostDis(Queue<Point> qu, int[][] dis) {
        while (!qu.isEmpty()){
            Point cn = qu.poll();

            for(int d = 0; d<DX.length; d++){
                int nx = cn.x + DX[d];
                int ny = cn.y + DY[d];

                if(isOutOfRange(nx, ny) || dis[nx][ny] <= dis[cn.x][cn.y] + 1) continue;

                dis[nx][ny] = dis[cn.x][cn.y] + 1;
                qu.add(new Point(nx, ny));
            }
        }
    }

    private static boolean isOutOfRange(int x, int y){
        return x < 0 || y < 0 || x >= n || y >= m;
    }

    private static class Point{
        int x, y;

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