동굴 탐험

문제 보기 · Level 4 · 2020 카카오 인턴십 · 정답률 20% · 푼 사람 1,886명 (2026-09-30 기준)¹

문제

방 n개(0 ~ n − 1)가 양방향 통로로 이어진 나무 모양 동굴이다. 입구는 0번 방이다. 모든 방을 적어도 한 번 방문해야 하고, “A번 방을 B번 방보다 먼저 방문해야 한다”는 순서 쌍들이 있다(방마다 쌍에 많아야 한 번 나온다). 규칙을 지키며 모든 방을 탐험할 수 있으면 true, 아니면 false를 돌려준다.

2 ≤ n ≤ 200,000, 통로 n − 1개
순서 쌍 1 ~ n/2개

풀이

막히면 한 단계씩 펼친다.

필요한 개념

너비 우선 탐색(BFS): 0번 방에서 BFS를 해 방마다 부모(0번 쪽으로 한 칸 가까운 방)를 구한다.
부분순서와 위상 정렬: “먼저 가야 하는 관계”들에 사이클이 없으면 순서를 정할 수 있다. 칸 방식(들어오는 화살표가 없는 방부터 떼기)으로 확인한다.
트리: 0번 방에서 어느 방까지 가는 길은 하나뿐이라, 어느 방이든 처음 닿기 전에 그 부모 방을 지난다. 그래서 “부모 → 자식” 화살표가 생긴다.

1단계 · 작은 예로 손으로 풀기

방 0 – 1 – 2가 한 줄로 있고, 순서 쌍이 [2, 1](2를 1보다 먼저)이라 하자.

2에 가려면 1을 지나야 한다. 1을 지나는 순간 1을 방문한 것이다.
그런데 1은 2보다 나중이어야 한다. 불가능하다.

즉 나무에서는 “부모를 먼저 방문해야 자식에 간다”는 순서가 저절로 생긴다. 이것과 주어진 순서 쌍을 모두 화살표로 그렸을 때 고리(사이클)가 생기면 불가능하다. 여기서는 1 → 2(나무)와 2 → 1(순서 쌍)이 고리다.

2단계 · 가장 단순한 방법과 그 속도

방을 처음 방문하는 순서를 모두 해 보면 (n − 1)!가지다. 20만 개면 어림없다.

3단계 · 핵심 아이디어

화살표 모으기: 0번에서 BFS로 부모를 구하고, “부모 → 자식” 화살표를 만든다. 순서 쌍 [A, B]도 “A → B” 화살표로 더한다.
가능 = 고리 없음: 화살표를 모두 지키는 방문 순서가 있으면 탐험할 수 있다. 나무에서는 이미 방문한 방들을 거쳐 다음 방까지 걸어가면 되기 때문이다. 그런 순서는 화살표에 고리가 없을 때만 있다.
고리 확인(칸 방식 위상 정렬): 들어오는 화살표 수(진입 차수)가 0인 방을 큐에 넣고, 꺼낼 때마다 그 방이 가리키는 방들의 수를 1 줄인다. 0이 되면 큐에 넣는다. 모든 방을 꺼냈으면 고리가 없다.
0번 방이 순서 쌍의 “나중”에 있으면 0번의 진입 차수가 0이 아니라 처음부터 막히니, 따로 처리하지 않아도 false가 나온다.

4단계 · 코드 흐름

통로로 인접 리스트를 만든다.
0번에서 BFS를 하며 부모 → 자식 화살표를 만들고 진입 차수를 센다.
순서 쌍 [A, B]마다 A → B 화살표를 더하고 B의 진입 차수를 1 늘린다.
진입 차수 0인 방부터 떼어 가며 뗀 방 수를 센다. n개면 true.

5단계 · 파이썬 코드

from collections import deque

def solution(n, path, order):
    graph = [[] for _ in range(n)]
    for a, b in path:
        graph[a].append(b)
        graph[b].append(a)
    succ = [[] for _ in range(n)]              # "먼저 → 나중" 화살표
    indeg = [0] * n
    parent = [-1] * n
    parent[0] = 0
    q = deque([0])
    while q:                                   # BFS로 부모 → 자식 화살표
        v = q.popleft()
        for u in graph[v]:
            if parent[u] == -1:
                parent[u] = v
                succ[v].append(u)
                indeg[u] += 1
                q.append(u)
    for a, b in order:                         # 순서 쌍 화살표
        succ[a].append(b)
        indeg[b] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    done = 0
    while q:                                   # 위상 정렬(칸 방식)
        v = q.popleft()
        done += 1
        for u in succ[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    return done == n

parent[0] = 0: 0번을 “이미 부모가 정해진 방”으로 표시해 BFS가 0으로 되돌아가지 않게 한다.
재귀 DFS 대신 BFS와 반복문을 써서, 방이 한 줄로 20만 개 이어져도 재귀 한도에 걸리지 않는다.

6단계 · 실행 추적

예시 1과 예시 3은 같은 동굴이다(부모: 1, 3, 7은 0, 8·2는 1, 6은 3, 4·5는 7).

예시	순서 쌍	떼어 낸 방 순서	결과
1	8 → 5, 6 → 7, 4 → 1	0, 3, 6, 7, 4, 1, 8, 2, 5	9개 모두 → true
3	4 → 1, 8 → 7, 6 → 5	0, 3, 6	3개에서 멈춤 → false

예시 3에서는 1 → 8(나무), 8 → 7(순서), 7 → 4(나무), 4 → 1(순서)이 고리다. 1, 8, 7, 4는 서로를 기다려 진입 차수가 0이 되지 않는다.

7단계 · 복잡도와 흔한 실수

BFS와 위상 정렬 모두 \(O(n)\)이다. 방 20만 개로 재 보니 0.2초가 안 걸렸다.

재귀 DFS로 부모를 구하다 RecursionError가 난다.
통로를 한 방향으로만 넣어 BFS가 방을 빠뜨린다(통로 쌍의 순서는 제멋대로다).
순서 쌍만 보고 사이클을 찾아, 나무에서 생기는 “부모 먼저” 조건을 빠뜨린다.

검증: 문제의 예시 3개를 통과했고, 6단계의 떼어 낸 방 순서와 예시 3의 고리를 코드로 확인했다. 무작위 동굴 2,000개(방 7개 이하)에서 “방을 처음 방문하는 순서를 모두 해 보는” 풀이, “실제로 돌아다니며 아직 못 들어가는 방을 대기시키는” 풀이와 결과가 모두 같았다. 방 20만 개의 시간도 쟀다 — 24_pg67260_p1.py

프로그래머스 스쿨, “동굴 탐험” (https://school.programmers.co.kr/learn/courses/30/lessons/67260), 2026-09-30 조회. ↩