문제 보기 · Level 3 · 2022 KAKAO TECH INTERNSHIP · 정답률 33% · 푼 사람 4,741명 (2026-09-30 기준)1
문제
지점 n개가 이동 시간이 있는 양방향 등산로로 이어져 있다. 지점은 출입구, 쉼터, 산봉우리 중 하나이고, 쉼터와 산봉우리에서는 쉴 수 있다. 한 출입구에서 출발해 산봉우리 하나만 들렀다가 같은 출입구로 돌아오는 코스를 짠다. 다른 출입구는 지나지 않는다. 코스의 intensity는 쉬지 않고 이동하는 시간 중 가장 긴 시간이다. intensity가 최소인 코스의 [산봉우리 번호, intensity]를 돌려준다. 여럿이면 산봉우리 번호가 가장 작은 것을 고른다.
- 2 ≤ n ≤ 50,000, 등산로 n − 1 ~ 200,000개
- 이동 시간 1 ~ 10,000,000
- 어느 두 지점 사이에도 길이 있다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
다익스트라: 경로의 값을 “시간의 합”이 아니라 “가장 긴 구간”으로 바꿔도, 길을 이을 때 값이 줄지 않으니 다익스트라가 그대로 통한다.
1단계 · 작은 예로 손으로 풀기
쉼터마다 쉴 수 있으니, 쉬지 않고 가는 시간은 곧 등산로 하나의 시간이다. 그래서 intensity는 “코스에서 지나는 등산로 중 가장 긴 것”이다.
올라간 길을 그대로 내려오면 내려오는 길의 가장 긴 구간도 같다. 그러니 올라가는 길만 생각하면 된다. “출입구에서 산봉우리까지, 가장 긴 구간이 가장 짧은 길”을 찾는 문제다.
예시 1(출입구 1, 3, 산봉우리 5)에서 1 → 2(3) → 4(2) → 5(3)는 가장 긴 구간이 3이다. 3 → 2(5)로 시작하면 이미 5다. 답은 [5, 3]이다.
2단계 · 가장 단순한 방법과 그 속도
출입구와 산봉우리 쌍마다 모든 길을 보면 길의 수가 폭발한다. “가장 긴 구간이 x 이하인 길만 써서 닿나?”를 이분 탐색하는 방법도 있지만, 출입구·산봉우리가 많으면 쌍마다 따로 해야 한다.
3단계 · 핵심 아이디어
- 다익스트라의 합을 max로: inten[v]를 “출입구에서 v까지 가는 길의 가장 긴 구간 중 최솟값”으로 둔다. v에서 w짜리 길로 u에 가면 그 길의 값은 max(inten[v], w)다. 이 값은 inten[v]보다 작아지지 않으니, “가장 작은 것부터 확정”이 합일 때처럼 맞다.
- 출입구를 모두 출발점으로: 출입구를 전부 값 0으로 힙에 넣는다. 다른 출입구를 지나가는 길은 그 출입구에서 새로 출발한 길과 같거나 나쁘다. 그래서 “다른 출입구를 지나지 않는다”는 규칙이 저절로 지켜진다.
- 산봉우리에서 멈추기: 산봉우리에 닿으면 거기서 더 나가지 않는다. 산봉우리를 두 개 지나는 코스를 막는다.
- 답: 산봉우리마다 (inten, 번호) 중 가장 작은 것.
4단계 · 코드 흐름
- 인접 리스트를 만들고, 산봉우리 표시를 한다.
- inten을 무한대로 채우고, 출입구는 0으로 힙에 넣는다.
- 힙에서 꺼낸 값이 낡았거나 산봉우리면 넘어간다. 아니면 이웃 u마다 max(값, w)로 줄여 본다.
- 산봉우리들의 (inten, 번호) 중 최소를 [번호, inten]으로 돌려준다.
5단계 · 파이썬 코드
import heapq
def solution(n, paths, gates, summits):
graph = [[] for _ in range(n + 1)]
for i, j, w in paths:
graph[i].append((j, w))
graph[j].append((i, w))
is_summit = [False] * (n + 1)
for s in summits:
is_summit[s] = True
INF = float("inf")
inten = [INF] * (n + 1)
heap = []
for g in gates: # 출입구를 모두 출발점으로
inten[g] = 0
heap.append((0, g))
heapq.heapify(heap)
while heap:
d, v = heapq.heappop(heap)
if d > inten[v] or is_summit[v]: # 낡았거나 산봉우리면 더 나가지 않는다
continue
for u, w in graph[v]:
nd = max(d, w) # 합이 아니라 가장 긴 구간
if nd < inten[u]:
inten[u] = nd
heapq.heappush(heap, (nd, u))
best = min((inten[s], s) for s in summits)
return [best[1], best[0]]
heapq.heapify(heap): 여러 출발점을 한 번에 힙으로 만든다.min((inten[s], s) for s in summits): 튜플은 앞 칸부터 비교하니, intensity가 같으면 번호가 작은 산봉우리가 뽑힌다.is_summit을 리스트로 두어 “산봉우리인가”를 \(O(1)\)에 본다.v in summits(리스트)로 쓰면 매번 훑어 느리다.
6단계 · 실행 추적
예시 1: 출입구 1, 3, 산봉우리 5, 등산로 1–2(3), 2–3(5), 2–4(2), 2–5(4), 3–4(4), 4–5(3), 4–6(1), 5–6(1)
| 꺼낸 (값, 지점) | 한 일 | 바뀐 inten |
|---|---|---|
| (0, 1) | 출입구에서 출발 | 2: 3 |
| (0, 3) | 출입구에서 출발 | 4: 4 (2는 max(0, 5) = 5라 그대로) |
| (3, 2) | 이웃 줄이기 | 4: max(3, 2) = 3, 5: 4 |
| (3, 4) | 이웃 줄이기 | 5: max(3, 3) = 3, 6: 3 |
| (3, 5) | 산봉우리, 멈춤 | |
| (3, 6) | 줄일 것 없음 |
낡은 기록 (4, 4), (4, 5)는 꺼낸 뒤 버린다. 산봉우리 5의 inten이 3이라 답은 [5, 3]이다.
7단계 · 복잡도와 흔한 실수
다익스트라와 같아 \(O((n + m) \log m)\)이다. 지점 5만 개, 등산로 20만 개로 재 보니 0.3초 안팎이었다.
- 출입구마다 따로 다익스트라를 돌려 출입구가 많을 때 시간 초과가 난다.
- 산봉우리에서 멈추지 않아 산봉우리를 거쳐 가는 길을 허용한다.
- 올라갔다 내려오는 길을 모두 계산하려고 상태를 복잡하게 만든다. 같은 길로 내려오면 되니 올라가는 길만 보면 된다.
- 합(
d + w)으로 계산한다. intensity는 가장 긴 구간(max(d, w))이다.