[Java] 2020 카카오 인턴십 (동굴 탐험)

문제 설명

---

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

오지 탐험가인 프로도는 탐험 도중 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번 방을 방문해야 함을 나타냅니다.

---

입출력 예

npathorderresult

9	[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]	[[8,5],[6,7],[4,1]]	true
9	[[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]]	[[4,1],[5,2]]	true
9	[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]	[[4,1],[8,7],[6,5]]	false

입출력 예에 대한 설명

 

 

접근 방법

---

 결론부터 이야기하자면 DFS를 사용하여 구현하였습니다. 효율성 10번 테스트케이스에서 런타임에러가 발생하는데 Java 환경에서는 BFS를 사용해야만 통과할 수 있을 거 같습니다. C++의 경우 DFS를 사용해도 무난히 통과할 수 있습니다.

 

이런 유형의 문제는 처음이여서 다른 사람들의 풀이를 참조하였습니다.

*order에서 [A -> B]가 존재한다고 할 때 A를 B의 사전노드, B를 A의 사후노드라고 표현하겠습니다.

 

1. 현재 방문하고자 하는 노드가 사전 노드를 가지고 있는지 확인합니다.

2. 사전 노드가 방문이 된 상태라면 DFS를 계속 진행합니다.

3. 사전 노드가 방문이 되지 않은 상태라면 현재 노드와 사전 노드를 reserve에 기록하고 DFS진행을 멈춥니다.

4. 이후 현재노드가 reserve에 기록되어 있다면, 즉시 사후노드부터 DFS를 진행시킵니다.

 

자세한 내용은 소스코드에 주석처리 하겠습니다.

 

소스 코드

---

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>(); //인접 리스트
    HashMap<Integer, Integer> before = new HashMap<Integer, Integer>(); //(사후노드, 사전노드)
    HashMap<Integer, Integer> reserve = new HashMap<Integer, Integer>(); //(사전노드, 사후노드)
    boolean visited[] = new boolean[200000];
    int cnt = 0; //노드의 방문 횟수
    
    public void init(int n, int[][] path, int[][] order){
        
        for(int i=0;i<n;i++)
            tree.add(new ArrayList<Integer>());
        for(int i=0;i<order.length;i++)
            before.put(order[i][1], order[i][0]);
        
        for(int i=0;i<path.length;i++){
            tree.get(path[i][0]).add(path[i][1]);
            tree.get(path[i][1]).add(path[i][0]);
        }    
    }
    
    public void DFS(int now){
        
        //사전노드를 가지고 있는지 검사
        if(before.get(now) != null){
        	//사전 노드가 방문된 상태가 아니라면 기록 후 진행을 멈춤
            if(!visited[before.get(now)]){
                reserve.put(before.get(now), now);
                return;
            }
        }
        
        visited[now] = true;
        ++cnt; //노드의 방문 횟수
        
        //만약 사후노드가 방문되었다면 사전 노드부터 탐색
        if(reserve.get(now) != null)
            DFS(reserve.get(now));
        
        //인접한 노드들로 DFS진행
        for(int i=0;i<tree.get(now).size();i++){
            int next = tree.get(now).get(i);
            if(!visited[next])
                DFS(next);
        }
        return;
    }
    
    public boolean solution(int n, int[][] path, int[][] order) {
        boolean answer = true;
        init(n, path, order); DFS(0);
        //모든 노드를 방문했다면 true, 아니면 false
        return answer = (cnt == n) ? true : false;
    }
}