[프로그래머스] 동굴탐험

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

트리 구조로 이루어진 노드들을 모두 방문 할 수 있는지 확인하는 문제

deque 자료구조를 활용하여 방문 필요조건, 연결된 이전 노드 방문 여부를 확인하면서 진행

from collections import deque, defaultdict

def solution(n, path, order):
    answer = True
    visited = [False] * n ## 모두 방문되어야 함 
    graph = [[] for _ in range(n)]
    for s, e in path:
        graph[s].append(e)
        graph[e].append(s)
    
    before = [0] * n # 이전 노드가 방문 되었는지 체크
    ancesor = [1] * n # 필수 방문이 열렸는지 
    
    front_check = defaultdict(int) # 여기를 방문했을때, 열리는 곳을 저장

    for a, b in order:
        front_check[a] = b
        ancesor[b] = 0
        
    q = deque()
    
    # 0도 방문가능 여부를 판별 해야함
    if ancesor[0]:
        q.append(0)
    
    while q:
        node = q.popleft()
        if front_check[node]:
            ancesor[front_check[node]] = 1
            if before[front_check[node]]:
                q.append(front_check[node])
                
        visited[node] = True
        
        for next in graph[node]:
            if visited[next]:
                continue
                
            before[next] = 1
            
            if ancesor[next]:
                q.append(next)
            
    return visited == [True] * n

• TC 30번이 틀린다면, 0이 무조건 방문 가능한건 아니란걸 알아야함.