[2020 카카오 인턴십 / 프로그래머스] 동굴 탐험 for JAVA

programmers.co.kr/learn/courses/30/lessons/67260

코딩테스트 연습 - 동굴 탐험

[문제 설명]

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다.

탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다.

1. 모든 방을 적어도 한 번은 방문해야 합니다.
2. 특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다.
   2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
   2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
   2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
   2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.

위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이 A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일

함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다.

• A → B, A → C (방문순서 배열 order = [...,[A,B],...,[A,C],...]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우
• X → A, Z → A (방문순서 배열 order = [...,[X,A],...,[Z,A],...]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상인 경우
• A → B → C (방문순서 배열 order = [...,[A,B],...,[B,C],...) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우

그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다.

방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• n은 2 이상 200,000 이하입니다.
• path 배열의 세로(행) 길이는 n - 1 입니다.
  • path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
  • 두 방 A, B사이를 연결하는 통로를 나타냅니다.
  • 통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
• order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
  • order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
  • A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.

동굴 그림은 아래와 같습니다.

[풀이]

이 문제의 목표는 전체 방을 탐험했는지 안 했는 지다. 내가 생각하는 중요한 조건은 다음과 같다.

1. 어떤 방은 그 방을 들어가기 전 꼭 먼저 들려야 하는 방이 있다.

2. 2개 이상의 방에 대해 먼저 들러야 하는 방이 같은 경우는 없다.

3. A -> B -> A 식의 이상한 조건은 없다.

 

x번에 방에 들어가려고 한다. 하지만 x방에 들어가려면 y방에 꼭 들어가야 한다.

그럼 우리는 일단 y방이 visited인지 확인한다. dfs나 bfs에서 흔히 존재하는 boolean형 배열에서 말이다.

방문 기록이 없으면 문제 될 것 없이 진행하지만 있다면은 우리는 y를 먼저 들려야 한다.

들려야할곳[y] = x. <- y를 들려야 x를 들린다. <- 설정해준 뒤 return, 또는 continue

 

이후 y방을 들렸을 때  q.add(들려야할곳[y])을 해주면 된다.

(이 로직은 모든 정점에서 한번씩 나온다. -> 모든 정점이 먼저 들려야 할 곳이 있어야 하는 건 아닌데 왜? -> 어차피 설정 안 돼있으면 0이다. 그렇다는 것은 바로 return이나 continue를 만난다는 말이다.)

 

BFS를 사용했다. 같은 맥락으로 DFS를 사용해도 충분하다. 

 

주의사항*

시작 지점 0이 먼저 들려야 하는 방이 있다면 그 케이스는 false이다.

 

[코드]

    int[] before;
    int[] savePoint;
    ArrayList<ArrayList<Integer>> map;
    boolean[] visited;
 
    public boolean solution(int n, int[][] path, int[][] order) {
        map = new ArrayList<ArrayList<Integer>>();
        before = new int[n];
        savePoint = new int[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) { //
            map.add(new ArrayList<Integer>());
        }
 
        for (int i = 0; i < path.length; i++) { // 그래프 생성
            map.get(path[i][0]).add(path[i][1]);
            map.get(path[i][1]).add(path[i][0]);
        }
 
        for (int i = 0; i < order.length; i++) { // 탐험 순서 저장
            before[order[i][1]] = order[i][0];
        }
        
        if(before[0] != 0) {                     //0이 먼저 들려야하는 정점이 있다면 false
            return false;
        }
        
        visited[0] = true;
        Queue<Integer> q = new LinkedList<>();
        for(int i : map.get(0)) {
            q.add(i);
        }
        while (!q.isEmpty()) {
            int e = q.remove();
 
            if (visited[e]) {
                continue;
            }
 
            if (!visited[before[e]]) {
                savePoint[before[e]] = e;
                continue;
            }
 
            visited[e] = true;
            for (int i : map.get(e)) {
                q.add(i);
            }
 
            q.add(savePoint[e]);
        }
 
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }
 
        return true;
    }
 

테스트 케이스 통과

 

느낀 점: 처음엔 위상정렬을 생각했다. 근데 굳이 위상정렬까지 갈 필요 없던 로직이었다. 좀 더 연습량을 늘려서 문제를 보고 가장 최선의 문제 풀이 방식을 떠올릴 수 있게 해야겠다.