Softeer_LV3_나무섭지

문제 링크

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

 

문제 요약

그림에서 사람은 남우라는 주인공입니다.

남우는 탈출구로 탈출해야하고, 유령과 만나면 안됩니다.
남우는 벽으로는 이동할 수 없어요.

유령은 벽도 이동 가능합니다.
그리고 현재자리에 머무를 수 있고 상하좌우로도 이동가능합니다.

풀이

이번 문제는 시간복잡도를 딱히 신경안써도 되는 문제였고, 방문처리에서 실수하면 메모리 초과를 발생할 수 있다고 생각했다.
n,m은 최대 1000, bfs를 5방향으로 해서 O(n*m*5) == 5백만 시간복잡도로 풀이 가능 
그리고, 방문처리할 때 얼만큼 메모리를 사용하는지 확인해봤습니다.
v[1000][1000][5]가 최대일때, boolean타입은 1비트인데 배열은 1바이트라고합니다.
그래서 1바이트 *5백만 = 5 MB정도 사용합니다. 여유여유

BFS를 사용하여 유령과 남우를 이동시켜서 이동이 끝난 후에 남우만 탈출한 경우 정답처리했습니다.

BFS를 구현하면서 남우가 먼저 이동하고 유령이 이동하면 둘은 겹치기 때문에 더이상 그 경우는 보지않아도 됩니다.
이런 로직을 어떻게 구현해야하지 고민하다가, "응? 남우는 빈칸이나 탈출구로만 이동하게 하면 되는데? 그럼 유령을 먼저 이동시켜두면 겹치는 경우가 자동처리되잖아?" 라는 생각을 했고, 그래서 bfs에서 큐에 삽입할 때 남우만 나중에 따로 삽입한 것이지요.

그리고 남우는 제자리에 있으면 안되니까 이동하는 방향을 나타내는 인덱스 0번인 경우는 무시했습니다.

기저조건
특별히 처리를 하지않으면 유령과 남우 모두 탈출해버리기 때문에 몇번 움직여서 탈출에 성공했는지 기록을 해야합니다.
그리고 누군가가 탈출했다면, 누가했는지를 알 수 있게 ghostGoal, namGoal을 변수로 활용하였고, goalCnt를 활용해 최초에 탈출할 때 몇번 움직였는지 기록합니다.
만약, 5번만에 탈출 성공했다면, 유령과 남우 모두 5번움직인 경우까지만 봐야합니다. 

package Softeer;

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

public class Softeer_LV3_나무섭지 {
    static boolean ghostGoal, namGoal; // 둘다 t면 실패, 남우만 t면 성공
    static int n, m, goalCnt, namI, namJ;
    static char map[][];
    static ArrayList<WhoAmI> whoami;

    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());

        whoami = new ArrayList<>();

        map = new char[n][m];

        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = input.charAt(j);
                if (map[i][j] == 'G') {
                    whoami.add(new WhoAmI(i, j, 0, 0, false));
                } else if (map[i][j] == 'N') {
                    namI = i;
                    namJ = j;
                }
            }
        }

        goalCnt = -1;
        bfs();

        // 남우만 탈출했다면 성공!
        if (namGoal && !ghostGoal) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    private static class WhoAmI {
        int ci, cj, cnt, preDir; // 현재 위치, 이동횟수, 이전 방향
        boolean isNam;

        public WhoAmI(int ci, int cj, int cnt, int preDir, boolean isNam) {
            this.ci = ci;
            this.cj = cj;
            this.cnt = cnt;
            this.preDir = preDir;
            this.isNam = isNam;
        }
    }

    private static void bfs() {
        // 현재자리, 상, 하, 좌, 우
        int[] di = {0, -1, 1, 0, 0};
        int[] dj = {0, 0, 0, -1, 1};

        Queue<WhoAmI> q = new LinkedList<>();
        boolean[][][] v = new boolean[n][m][5]; // 위치 i,j와 이전에 어떤 방향에서 왔는지 기록하여 방문체크한다.

        // 유령이 먼저 움직이게하고 남우는 나중에 움직여야한다.
        //  유령과 남우가 겹치지 않게 움직이기 위함.
        // 유령들 먼저 방문처리와 큐에 넣어줌.
        for (WhoAmI w : whoami) {
            q.offer(w);
            v[w.ci][w.cj][0] = true;
        }
        // 남우도 큐에 넣어줌
        q.offer(new WhoAmI(namI, namJ, 0, 0, true));
        v[namI][namJ][0] = true;

        while (!q.isEmpty()) {
            WhoAmI cur = q.poll();

            //기저조건 도착했고 도착한 숫자보다 커지면 그만.
            if ((ghostGoal || namGoal)) {

                if (goalCnt == -1) { // 처음 탈출에 도착했을때 이동한 개수 체크 (종료조건에 사용)
                    goalCnt = cur.cnt;
                }

                if (goalCnt != 1 && cur.cnt > goalCnt) return; // 이미 탈출에 성공했다면 그만
            }

            int ni, nj;
            for (int i = 0; i < 5; i++) {
                ni = cur.ci + di[i];
                nj = cur.cj + dj[i];

                // 범위 내 확인
                if (isIn(ni, nj)) {
                    // 유령과 남우를 구분해서 로직
                    if (cur.isNam) { // 남우면 벽이거나, 유령이 없는 곳으로 이동 후 큐삽입
                        // 남우는 이동해야만함
                        // 미방문, 이동가능, 탈출구면 이동.
                        if (i != 0 && (map[ni][nj] == '.' || map[ni][nj] == 'D') && !v[ni][nj][cur.preDir]) {

                            if (map[ni][nj] == 'D') { // 탈출했다면 탈출을 알림.
                                namGoal = true;
                                if (goalCnt == -1) {
                                    goalCnt = cur.cnt + 1;
                                }
                            } else {
                                v[ni][nj][cur.preDir] = true;
                                q.offer(new WhoAmI(ni, nj, cur.cnt + 1, i, cur.isNam));
                            }
                        }
                    } else {
                        // 유령은 벽 무시하고 이동가능, 방문이 겹치지않으면 이동한다.
                        if (!v[ni][nj][cur.preDir]) {

                            if (map[ni][nj] == 'D') { // 탈출했다면 탈출을 알림.
                                ghostGoal = true;
                                if (goalCnt == -1) {
                                    goalCnt = cur.cnt + 1;
                                }
                            } else {
                                v[ni][nj][cur.preDir] = true;
                                q.offer(new WhoAmI(ni, nj, cur.cnt + 1, i, cur.isNam));
                            }
                        }
                    }
                }
            }
        }
    }

    private static boolean isIn(int ni, int nj) {
        return 0 <= ni && ni < n && 0 <= nj && nj < m;
    }
}