문제 보기 · Level 4 · 2021 카카오 채용연계형 인턴십 · 정답률 10% · 푼 사람 1,154명 (2026-09-30 기준)1
문제
방 n개와 한 방향 길들이 있다. 길마다 걸리는 시간이 있다. 몇몇 방은 함정이다. 함정 방에 들어가는 순간 그 방에 붙은 모든 길의 방향이 반대로 바뀐다. 같은 함정에 다시 들어가면 또 뒤집힌다. start에서 end까지 가는 최소 시간을 돌려준다.
- 2 ≤ n ≤ 1,000, 길 1 ~ 3,000개, 시간 1 ~ 3,000
- 함정 0 ~ 10개, start와 end는 함정이 아니다, 늘 탈출할 수 있다
풀이
막히면 한 단계씩 펼친다.
필요한 개념
- 다익스트라: 시간이 다른 길로 최소 시간을 구한다. 점은 “방 + 지금 켜진 함정들”이다.
- 비트 연산과 비트마스크: 함정이 10개 이하라 켜짐·꺼짐을 비트 10개(수 하나)로 나타낸다.
- 불 대수와 논리 회로: 함정의 켜짐은 들어간 횟수의 홀짝(패리티)이라 들어갈 때마다 XOR로 뒤집는다. 길이 뒤집혔는지도 두 끝 방의 켜짐을 XOR한 값(코드의
!=)이다.
1단계 · 작은 예로 손으로 풀기
예시 1: 길 1 → 2(2), 3 → 2(3), 함정 2. 1에서 3으로 간다.
- 1 → 2로 간다(2초). 함정 2가 켜져 2에 붙은 길이 뒤집힌다. 1 → 2는 2 → 1이 되고, 3 → 2는 2 → 3이 된다.
- 2 → 3으로 간다(3초). 합 5초다.
길의 방향은 “양 끝 방 중 켜진 함정이 몇 개인가”로 정해진다. 하나만 켜져 있으면 한 번 뒤집힌 상태, 둘 다 켜져 있거나 둘 다 꺼져 있으면 원래 방향이다(두 번 뒤집히면 제자리).
2단계 · 가장 단순한 방법과 그 속도
길 3,000개의 방향을 모두 상태로 들고 다니면 상태가 2³⁰⁰⁰가지까지 생길 수 있다. 하지만 길 방향은 함정 10개의 켜짐·꺼짐만으로 정해지니, 상태는 방 1,000 × 2¹⁰ = 약 100만 개로 충분하다. 켜진 함정들은 함정 10개의 부분집합이고, 부분집합(멱집합의 원소)은 2¹⁰가지다. 상태는 (방, 부분집합) 순서쌍이라, 이 수는 집합의 곱집합 크기다.
3단계 · 핵심 아이디어
- 상태 = (방, 켜진 함정 비트): 함정마다 비트 자리를 하나 정한다. mask의 i번째 비트가 1이면 i번째 함정이 켜져(홀수 번 들어가) 있다.
- 길을 쓸 수 있나: 원래 방향 p → q인 길은, p와 q 중 켜진 함정이 정확히 하나면 뒤집혀 q → p로만, 아니면 p → q로만 쓴다. 그래서 길마다 양쪽 방에서 볼 수 있게 넣고, “원래 방향으로 가려는가”와 “지금 뒤집혔나”를 비교한다.
- 함정에 들어가면: 새 방이 함정이면 mask의 그 비트를 뒤집는다(
mask ^ (1 << i)). - 다익스트라: 이 상태 그래프에서 시간은 모두 양수라 다익스트라가 맞다. end 방이 처음 꺼내지는 순간의 시간이 답이다(mask는 무엇이든 된다).
4단계 · 코드 흐름
- 함정 번호 → 비트 자리 딕셔너리를 만든다.
- 길 p → q(시간 s)를 adj[p]에 (q, s, 원래 방향), adj[q]에 (p, s, 반대 방향)으로 넣는다.
- (start, 0)에서 다익스트라를 한다. 방 v에서 각 길에 대해 “뒤집혔나 = on(v) ≠ on(u)”를 구하고, 원래 방향 길은 안 뒤집혔을 때, 반대 방향 길은 뒤집혔을 때만 간다.
- u가 함정이면 비트를 뒤집은 mask로 간다. end를 꺼내면 그 시간을 돌려준다.
5단계 · 파이썬 코드
import heapq
def solution(n, start, end, roads, traps):
tid = {t: i for i, t in enumerate(traps)} # 함정 → 비트 자리
adj = [[] for _ in range(n + 1)]
for p, q, s in roads:
adj[p].append((q, s, True)) # 원래 방향 p → q
adj[q].append((p, s, False)) # 뒤집혔을 때만 쓰는 q → p
def on(v, mask): # v가 켜진 함정인가
return v in tid and (mask >> tid[v]) & 1
INF = float("inf")
dist = {(start, 0): 0}
heap = [(0, start, 0)]
while heap:
d, v, mask = heapq.heappop(heap)
if d > dist[(v, mask)]:
continue
if v == end:
return d
for u, w, forward in adj[v]:
flipped = on(v, mask) != on(u, mask) # 한쪽만 켜졌으면 뒤집힌 상태
if forward == flipped:
continue # 지금 방향과 맞지 않는 길
nmask = mask ^ (1 << tid[u]) if u in tid else mask
nd = d + w
if nd < dist.get((u, nmask), INF):
dist[(u, nmask)] = nd
heapq.heappush(heap, (nd, u, nmask))
return -1 # 문제에서는 늘 탈출할 수 있다
on(...)은 참·거짓 대신 0, 1, False를 돌려줄 수 있다.!=로 비교하면 모두 “켜짐 여부”로만 비교된다. False와 0은 같게 본다.forward == flipped면 건너뛴다: 원래 방향 길(forward 참)인데 뒤집혔거나(flipped 참), 반대 방향 길(forward 거짓)인데 안 뒤집혔을(flipped 거짓) 때다.
6단계 · 실행 추적
예시 2: 길 1 → 2, 3 → 2, 2 → 4(모두 1초), 함정 2(비트 0), 3(비트 1). mask는 (함정 3, 함정 2) 순서의 두 자리로 쓴다.
| 상태 (방, mask) | 시간 | 다음으로 간 길 |
|---|---|---|
| (1, 00) | 0 | 1 → 2: 둘 다 꺼짐, 원래 방향 → 함정 2를 켠다 |
| (2, 01) | 1 | 2 → 3: 2만 켜짐 → 3 → 2가 뒤집혀 쓸 수 있다. 함정 3을 켠다. 2 → 4는 뒤집혀서 못 쓴다 |
| (3, 11) | 2 | 3 → 2: 둘 다 켜짐 → 원래 방향. 함정 2를 끈다 |
| (2, 10) | 3 | 2 → 4: 2 꺼짐, 4는 함정 아님 → 원래 방향 |
| (4, 10) | 4 | 도착 |
답은 4다(1 → 2 → 3 → 2 → 4). (2, 01)에서 2 → 1로 돌아가는 길(시간 2의 (1, 01))도 생기지만 거기서는 더 갈 곳이 없다.
7단계 · 복잡도와 흔한 실수
상태 n·2ᵗ개(t는 함정 수), 상태마다 그 방에 붙은 길을 본다. 방 1,000개, 길 3,000개, 함정 10개에서 거의 모든 상태를 돌게 만든 입력으로 재 보니 1.4초 안팎이었다.
- 함정 여부를 방만 보고 길 방향을 정한다. 양 끝이 둘 다 켜진 함정이면 원래 방향이다.
- 방 번호만 방문 표시해, 같은 방에 다른 함정 상태로 오는 경우를 버린다.
- 함정에 들어갈 때 비트를 켜기만 하고 끄지 않는다. 두 번째 들어가면 다시 꺼진다.
-
프로그래머스 스쿨, “미로 탈출” (https://school.programmers.co.kr/learn/courses/30/lessons/81304), 2026-09-30 조회. ↩