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

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

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

DFS에 조건을 잘 걸어야 하는 문제다

 

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
def solution(n, path, order):
    visited = [0]*n
    visited_count = 0
    graph = [[] for _ in range(n)]
    after = defaultdict(lambda : -1)
    ordered = [0]*n

    for p in path:
        start , end = p
        graph[start].append(end)
        graph[end].append(start)

    for o in order:
        pre, post = o
        ordered[post] = pre

    stack = [0]
    while stack:
        node = stack.pop()
        if ordered[node] and visited[ordered[node]] == False:
            after[ordered[node]] = node
            continue
        visited[node] = 1
        visited_count +=1
        for next in graph[node]:
            if visited[next] ==0:
                stack.append(next)
        if after[node] != -1:
            stack.append(after[node])
    return True if visited_count == n else False