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

 

 

programmers.co.kr/learn/challenges

코딩테스트 연습

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

 

 

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

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

• 모든 방을 적어도 한 번은 방문해야 합니다.

위 계획 중 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 이하입니다.

---

입출력 예

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

입출력 예에 대한 설명

입출력 예 #1

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

 

 

방문 순서를 지켜야 하는 방 번호는 다음과 같습니다.

• 6번 → 7번
• 4번 → 1번
• 8번 → 5번

따라서 모든 방을 방문할 수 있는 방법 중 하나는 다음과 같습니다.

• 0번 → 3번 → 6번 → 3번 → 0번 → 7번 → 4번 → 7번 → 0번 → 1번 → 8번 → 1번 → 2번 → 1번 → 0번 → 7번 → 5번

입출력 예 #2

 

 

다음 순서로 각 방을 방문하면 됩니다.

• 0번 → 7번 → 4번 → 7번 → 5번 → 7번 → 0번 → 3번 → 6번 → 3번 → 0번 → 1번 → 8번 → 1번 → 2번

입출력 예 #3

 

 

규칙에 맞게 모든 방을 방문할 수 있는 방법이 없습니다.

 

---

 

from collections import defaultdict

def solution(n, path, order):
    
    adj = [[] for _ in range(n)]
    
    visited = [False for _ in range(n)]
    
    for a,b in path:
        
        adj[a].append(b)
        adj[b].append(a)
    
    parent = defaultdict(int) # 0으로 default, key가 자식, value가 부모
    child = defaultdict(int) # key가 부모, value가 자식
    
    for o in order:
        parent[o[1]] = o[0] # key로 가기전에 value 먼저 가야함
    
    if 0 in parent.keys(): #0가기전에 어디들러야하면 안됨. 입구는 0뿐!
        return False
    
    stk = [0] # DFS로 풀어보장, 입구는 항상 0임
    
    while stk:
        
        curr = stk.pop()

        if curr in parent.keys() and not visited[parent[curr]]: # nxt부모있는데 부모는 방문안했다면 킵해놔야함. 부모가 방문할때 같이 처리해놓을거니까 키를 부모로 해놔야 찾기편함.
            child[parent[curr]] = curr
            continue #밑에 안하고 넘어감
        
        
        # 부모가 없거나 부모 이미 방문했음 이 아이도 방문 ok
        
        visited[curr] = True
        
        for nxt in adj[curr]:
            if not visited[nxt]:
                stk.append(nxt)
                
        # 자식 있는 경우? 이제 방문해도됨
        
        if curr in child.keys():
            
            stk.append(child[curr])
            
  
    if False in visited: 
        return False
    else: return True

오랜만에 코테 푸니까 재미지군