프로그래머스 동굴 탐험 python

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

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

1. 해결 방법

DFS에 방문순서가 정해져있는 경우가 합쳐져 있는 경우이다. 카카오 인턴쉽 해설을 보고 풀 수 있었다.

tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

먼저 시작점인 0번 정점부터 방문을 시작하는데 방문조건이 만족하지 않은 노드는 딕셔너리에 기록해둬서 조건이 만족되면 방문할 수 있도록 한다. 코드는 다음과 같다.

#모든 방을 적어도 한번은 방문
#특정 방 방문 전에 먼저 방문해야하는 방 존재

def solution(n, path, order):
	
    #path 정보로 부터 인접 리스트를 구현한다.
    tree = [[] for _ in range(n)]
    for v1, v2 in path:
        tree[v1].append(v2)
        tree[v2].append(v1)
      
    #어떤 방 X에 가기 위해 들러야하는 방은 1개이거나 존재하지 않음
    #orders[i] : i번째 방을 방문하기 위해 이전에 방문해야하는 노드
    orders =[0 for i in range(n)]
    for pre, post in order:
        orders[post] = pre
    
    
    num_visit = 0
    
    visited = [False for i in range(n)]
    q = [0]
    
    #방문해야하는 노드 : key에 있는 노드를 들른 후 갈 수 있는 노드
    after ={}
    
    while q:
        here = q.pop(0)
        
        #현재 위치를 방문하기전에 들러야하는 정점이 존재하고 아직 그 정점을 방문하지 않았다면 체크해둔다.
        #orders[here] : here를 방문하기 위해 이전에 방문해야하는 정점
        if orders[here] and not visited[orders[here]]:
            after[orders[here]] = here
            continue
        
        #위 조건을 통과하면 방문 가능
        visited[here] = True
        num_visit +=1
    	
        #현재 위치와 연결되어 있는 점들을 q에 추가해준다.
        for there in tree[here]:
            if not visited[there]:     
                q.append(there)
        
        #지금 방문하는 곳이 after에 포함되어 있다면 이제 현재 위치를 방문해야 갈 수 있는 정점으로 
        #이동가능하므로 이동가능 한 정점을 q에 넣어준다.
        
        if here in after:
            q.append(after[here])
                    
    return n == num_visit