45일차)알고리즘 문제(동굴 탐험)

>알고리즘 문제

1. 문제

문제 설명

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

2. 솔루션

class Solution {
    fun solution(n: Int, path: Array<IntArray>, order: Array<IntArray>): Boolean {
        
        val p=Array(n){HashSet<Int>()}
        for(i in path){
            p[i[0]].add(i[1])
            p[i[1]].add(i[0])
        }
        
        
        //order를 해시맵으로 저장(키가 끝, 값이 시작)
        val orders=HashMap<Int,Int>(order.size)
        for(i in order){
            orders.put(i[1],i[0])
        }
        
        if(orders.containsKey(0)) return false
        
        val q=ArrayDeque<Int>()
        val aft=HashSet<Int>()
        val befinit=HashMap<Int,Int>()
        aft.add(0)
        q.addLast(0)
        while(q.isNotEmpty()){
            val cur=q.removeFirst()
            
            //현재 노드가 저장된 끝노드에 상응하는 시작노드인 경우 끝노드를 해시셋과 큐에 넣음
            if(befinit.containsKey(cur)){
                val end=befinit[cur] as Int
                aft.add(end)
                q.addLast(end)
            }
            
            for(i in p[cur]){
                //해시셋에 있으면 넘어감
                if(aft.contains(i)) continue
                //끝노드이고 시작노드가 해시셋에 없는 경우:끝노드가 아닌경우는 무조건 있는 0으로 반환
                if(!aft.contains(orders.getOrElse(i){0})){
                    befinit.put(orders[i] as Int,i)
                }else{
                    aft.add(i)
                    q.addLast(i)
                }
            }  
        }
        
        if(aft.size==n) return true
        else return false

    }
    
}

-order를 해시맵에 저장하여 확인에 걸리는 시간을 최소화

-0부터 시작해 BFS로 탐색시작(이때 order에 0이 나중에 와야하는 경우를 걸러내고 시작)

-지나간 노드는 해시셋에 저장

-연결된 노드들을 체크해서 끝노드인데 시작노드가 아직 해시셋에 없으면 따로 저장

-이후 루프에서 따로저장된 끝노드에 상응하는 시작노드인지 체크해서 맞다면 끝노드를 그때 큐와 해시셋에 넣어줌

-이렇게 돌아서 while문을 벗어났을때 모든 노드를 탐색했다면 true, 아니면 false를 반환