title: "[프로그래머스] 동굴 탐험 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/67260"
description: "프로그래머스 Level 4 문제 [동굴 탐험]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

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

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges