동굴 탐험

from heapq import heappush, heappop from collections import defaultdict def solution(n, path, order): priority = {i:0 for i in range(n)} for u, v in order: priority[u] = -1 priority[v] = 1 allowedby = {} for u, v in order: allowedby[u] = v isallowed = set(range(n)) for _, v in order: isallowed.discard(v) # 처음에 0에 접근할 수 없으면 방문 불가 if 0 not in isallowed: return False A = defaultdict(list) for u, v in path: A[u].append(v) A[v].append(u) q, pending, vis = [], set(), set() heappush( q, (priority[0], 0) ) while q: _, u = heappop(q) vis.add(u) if u in allowedby: v = allowedby[u] isallowed.add(v) if v in pending: heappush( q, (priority[v], v) ) pending.discard(v) for v in A[u]: if v in isallowed: if v not in vis: heappush( q, (priority[v], v) ) else: if v not in vis: pending.add(v) return len(vis) == n