[소프티어] 나무 섭지 LV.3

문제

https://softeer.ai/practice/7726

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

 

 

자세한 내용은 원문 코드를 참조할 것.

 

풀이

유령이 과연 남우를 잡을 수 있을까? 에 대한 풀이는 간단하다.

BFS를 사용하여, '벽을 뚫을 수 있는' 유령의 최단거리보다 남우의 '최단거리' 가 짧으면 된다.

 

따라서, BFS를 유령 / 남우, 두 번씩 비교하여 최소값을 비교하면 된다.

 

여기서 시간 초과가 발생할 수 있는데, BFS의 범위 스코프를 '유령' 값의 스코프를 통해 비교해주면 된다.

전체 탐색의 경우 2.08초(처음에 시간 초과가 발생했다)였으나, 풀이 이후 0.1초 이내로 풀 수 있었다.

 

하위 코드에서는 'ghostDist'를 통해 스코프를 제한했다.

아래 코드에서 해당 프로퍼티를 중심으로 해석하면 쉬울 것이다.

 

코드

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

public class Main {
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};
    static int N, M;
    static boolean[][] map;
    static int[][] ghostDist;
    static boolean[][] visit;
    static int[] player;
    static int[] exit;
    static List<int[]> ghosts = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        input();
        logic();
    }

    public static void logic() {
        bfsGhosts(); // 유령들의 최소 거리 계산
        int minPlayerDist = bfsPlayer(); // 남우의 최소 거리 계산
        if (minPlayerDist == Integer.MAX_VALUE) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }

    public static void bfsGhosts() {
        Queue<int[]> bfsQ = new ArrayDeque<>();
        ghostDist = new int[N][M];
        for (int[] row : ghostDist) Arrays.fill(row, Integer.MAX_VALUE);

        for (int[] ghost : ghosts) {
            bfsQ.offer(new int[]{ghost[0], ghost[1], 0});
            ghostDist[ghost[0]][ghost[1]] = 0;
        }

        while (!bfsQ.isEmpty()) {
            int[] now = bfsQ.poll();
            int r = now[0], c = now[1], dist = now[2];
            for (int i = 0; i < 4; i++) {
                int nr = r + DR[i], nc = c + DC[i];
                if (cantGo(nr, nc) || dist + 1 >= ghostDist[nr][nc]) continue;
                ghostDist[nr][nc] = dist + 1;
                bfsQ.offer(new int[]{nr, nc, dist + 1});
            }
        }
    }

    public static int bfsPlayer() {
        Queue<int[]> bfsQ = new ArrayDeque<>();
        visit = new boolean[N][M];
        bfsQ.offer(new int[]{player[0], player[1], 0});
        visit[player[0]][player[1]] = true;

        while (!bfsQ.isEmpty()) {
            int[] now = bfsQ.poll();
            int r = now[0], c = now[1], dist = now[2];
            if (r == exit[0] && c == exit[1]) return dist;

            for (int i = 0; i < 4; i++) {
                int nr = r + DR[i], nc = c + DC[i];
                if (cantGo(nr, nc) || visit[nr][nc] || map[nr][nc] || dist + 1 >= ghostDist[nr][nc]) continue;
                visit[nr][nc] = true; // 방문 체크를 큐에 추가하기 전에 수행
                bfsQ.offer(new int[]{nr, nc, dist + 1});
            }
        }

        return Integer.MAX_VALUE;
    }

    public static boolean cantGo(int r, int c) {
        return r < 0 || c < 0 || r >= N || c >= M;
    }

    public static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                char now = s.charAt(j);
                if (now == '.') map[i][j] = false;
                else if (now == '#') map[i][j] = true;
                else if (now == 'D') exit = new int[]{i, j};
                else if (now == 'N') player = new int[]{i, j};
                else if (now == 'G') ghosts.add(new int[]{i, j});
            }
        }
    }
}