[Softeer] 나무 섭지 / Java

문제 출처

https://softeer.ai/practice/7726

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

문제 풀이

남우가 유령을 피해 목적지에 도달할 수 있는지의 여부를 판단하는 문제입니다.

 

남우와 유령이라는 두 종류의 움직이는 말이 있는 상황이므로

각각을 위한 Queue를 마련하여 BFS를 수행하며 이동가능한 칸에 대해 걸리는 시간 정보를 탐색해나갑니다.

 

여기서 주의할 점은 남우가 유령에 잡히지 않아야 된다는 것입니다.

따라서 canGoNamwoo() 메서드로 남우의 이동가능성을 파악할 때, 해당 칸에 대해 유령이 도달하는 시점과 남우가 도달하는 시점을 비교하는 것이 포인트입니다.

 

추가 설명은 코드의 흐름에 따라 주석으로 작성하였습니다.

Java Code

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 {

    static final int INF = 1_000_000_000;
    static int N, M;
    static char[][] map;
    static Queue<Point> ghost;
    static Queue<Point> namwoo;
    static int[][] visitedGhost;
    static int[][] visitedNamwoo;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static class Point {
        int x, y;

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

    public static void main(String[] args) throws IOException {
        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 char[N][M];
        ghost = new LinkedList<>();
        namwoo = new LinkedList<>();
        visitedGhost = new int[N][M];
        visitedNamwoo = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(visitedGhost[i], INF);
        }

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                char ch = str.charAt(j);
                switch (ch) {
                    case 'D': case '#':
                        map[i][j] = ch;
                        break;
                    case 'N':  // 남우
                        namwoo.add(new Point(i, j));
                        visitedNamwoo[i][j] = 1;
                        break;
                    case 'G':  // 유령
                        ghost.add(new Point(i, j));
                        visitedGhost[i][j] = 1;
                }
            }
        }

        bfsGhost();
        boolean result = bfsNamwoo();
        System.out.println(result ? "Yes" : "No");
    }

    /**
     * 유령에 대한 BFS
     */
    public static void bfsGhost() {
        while (!ghost.isEmpty()) {
            Point cur = ghost.poll();

            for (int d = 0; d < 4; d++) {
                int ni = cur.x + di[d];
                int nj = cur.y + dj[d];

                if (canMoveGhost(ni, nj)) {
                    visitedGhost[ni][nj] = visitedGhost[cur.x][cur.y] + 1;  // 새로운 칸으로 가는 데 걸리는 시간 저장
                    ghost.add(new Point(ni, nj));
                }
            }
        }
    }

    /**
     * 주어진 칸으로 유령이 이동할 수 있는 지 여부를 반환한다
     * @param i 이동할 칸의 행 인덱스
     * @param j 이동할 칸의 열 인덱스
     */
    public static boolean canMoveGhost(int i, int j) {
        if (i < 0 || j < 0 || i >= N || j >= M) return false;
        return visitedGhost[i][j] == INF;  // 이미 방문한 칸인 경우
    }

    /**
     * 남우에 대한 BFS
     * @return 남우가 목적지에 도달할 수 있으면 true를 반환한다
     */
    public static boolean bfsNamwoo() {
        while (!namwoo.isEmpty()) {
            Point cur = namwoo.poll();

            for (int d = 0; d < 4; d++) {
                int ni = cur.x + di[d];
                int nj = cur.y + dj[d];

                if (canMoveNamwoo(cur.x, cur.y, ni, nj)) {
                    visitedNamwoo[ni][nj] = visitedNamwoo[cur.x][cur.y] + 1;  // 새로운 칸으로 가는 데 걸리는 시간 저장
                    namwoo.add(new Point(ni, nj));

                    if (map[ni][nj] == 'D') return true;
                }
            }
        }

        return false;
    }

    /**
     * 현재 칸에서 다음 칸으로 남우가 이동할 수 있는 지 여부를 반환한다
     * @param i 현재 칸의 행 인덱스
     * @param j 현재 칸의 열 인덱스
     * @param ni 이동할 칸의 행 인덱스
     * @param nj 이동할 칸의 열 인덱스
     * @return 이동 가능 여부
     */
    public static boolean canMoveNamwoo(int i, int j, int ni, int nj) {
        if (ni < 0 || nj < 0 || ni >= N || nj >= M) return false;
        if (map[ni][nj] == '#') return false;
        if (visitedNamwoo[ni][nj] > 0) return false;  // 이미 방문한 칸인 경우
        return visitedGhost[ni][nj] > visitedNamwoo[i][j] + 1;  // 남우가 유령보다 더 빠른 시점에 해당 칸으로 가야만 가능
    }

}