순서대로 줄 세우자냥! 위상 정렬
안녕, 나 코딩냥이다냥! "이걸 하려면 저걸 먼저 해야 해" 같은 순서 조건이 잔뜩 있을 때, 어떤 차례로 일을 해야 하냥? 그걸 정하는 게 위상 정렬이라냥.
수강 신청(선수 과목), 요리 순서, 빌드 순서가 전부 이거라냥.
오늘의 학습 목표
- 진입 차수로 위상 정렬을 한다 (칸 알고리즘).
- 사전순으로 가장 빠른 순서를 구한다.
- 순서가 유일한지 판별한다.
- 사이클이 있으면 불가능함을 안다.
- 임계 경로로 최소 시간·최소 단계를 구한다.
1단계 · 진입 차수라냥 (10분)
핵심 개념은 진입 차수라냥. 어떤 일로 들어오는 화살표의 수라냥.
진입 차수가 0 이면, 먼저 할 게 없다는 뜻이라 지금 당장 할 수 있다냥.
비유로 이해하기 — 밀린 숙제
"수학 숙제를 하려면 교과서를 읽어야 한다" 처럼 선행이 있는 숙제가 있다냥. 선행이 하나도 없는 숙제(진입 차수 0)는 지금 바로 할 수 있다냥.
하나를 끝내면, 그걸 기다리던 숙제들의 선행이 하나 줄어든다냥. 그러다 선행이 다 없어지면(진입 차수 0) 그것도 할 수 있게 된다냥.
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split()) # a → b (a 를 먼저)
adj[a].append(b)
indeg[b] += 1 # b 로 들어오는 화살표 +12단계 · 칸 알고리즘 (13분)
진입 차수 아이디어로 순서를 뽑는 게 칸 알고리즘이라냥. 9장의 큐를 쓴다냥.
- 진입 차수가 0 인 일을 전부 큐에 넣는다
- 큐에서 하나 꺼내 순서에 추가한다
- 그 일의 이웃들의 진입 차수를 1 줄인다
- 진입 차수가 0 이 된 이웃을 큐에 넣는다
- 큐가 빌 때까지 반복한다
from collections import deque
q = deque(i for i in range(1, n + 1) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)꺼낸 순서 order 가 곧 위상 정렬 결과라냥. 선행을 먼저 꺼냈으니 규칙을
항상 지킨다냥.
3단계 · 사전순으로 가장 빠르게 (12분)
진입 차수 0 인 게 여러 개면, 어느 걸 먼저 꺼내도 규칙은 지킨다냥. 그런데 "번호가 작은 것부터" 처럼 조건이 붙으면, 큐 대신 우선순위 큐를 쓴다냥.
import heapq
pq = [i for i in range(1, n + 1) if indeg[i] == 0]
heapq.heapify(pq)
order = []
while pq:
u = heapq.heappop(pq) # 가장 작은 번호부터 꺼낸다냥
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
heapq.heappush(pq, v)큐를 그냥 쓰면 사전순이 안 나온다냥.
평범한 큐(deque)는 넣은 순서대로 꺼내니, 사전순 최소를 보장 못 한다냥.
"번호가 작은 것부터" 를 지키려면 최소 힙을 써야 한다냥. 18장 다익스트라의
우선순위 큐와 같은 도구라냥.
오늘 1번 문제가 이걸 잡는다냥.
같은 입력이라도 묻는 게 다를 수 있다냥. 오늘 2번은 "순서가 유일하냥?" 을 묻는다냥. 위상 정렬 도중 진입 차수 0 인 게 한 번이라도 둘 이상이면, 그 순간 갈림길이 있다는 뜻이라 순서가 여러 가지라냥.
4단계 · 사이클이 있으면 불가능이라냥 (10분)
"A 다음 B, B 다음 C, C 다음 A" 처럼 빙 도는 조건이 있으면 어떻게 되냥? 아무것도 시작을 못 한다냥. 이게 사이클이라냥.
뽑은 순서의 길이가 n 이 아니면 사이클이 있다냥.
사이클 안의 일들은 서로가 서로의 선행이라, 진입 차수가 영영 0 이 안 된다냥. 그래서 큐에 들어가지 못하고 순서에서 빠진다냥.
# 위상 정렬을 끝낸 뒤
print("YES" if len(order) == n else "NO")뽑힌 게 n개보다 적으면, 빠진 것들이 사이클을 이루고 있는 거라냥. 오늘
3번 문제라냥.
5단계 · 임계 경로 (13분)
위상 순서대로 훑으면, 각 일까지 가장 오래 걸리는 경로를 계산할 수 있다냥. 이걸 임계 경로라 한다냥. 13장 DP 의 냄새가 나지냥?
작업마다 시간이 있고, 서로 독립인 건 동시에 할 수 있다냥. 그러면 전체 완료 시간은 가장 긴 선행 사슬이 결정한다냥 (합이 아니라 최댓값).
finish = [0] * (n + 1)
for u in order: # 위상 순서로
finish[u] += time[u] # 선행들의 최대 끝시각 + 내 시간
for v in adj[u]:
finish[v] = max(finish[v], finish[u])
print(max(finish[1:]))finish[u] 는 u 가 끝나는 가장 이른 시각이라냥. 위상 순서로 훑으니
u 를 처리할 때 선행은 이미 다 계산돼 있다냥. 오늘 4번 문제라냥.
시간 대신 단계 수를 세면 오늘 5번 문제라냥. "한 단계에 할 수 있는 걸 다 동시에" 할 때 필요한 최소 단계는 가장 긴 사슬의 길이라냥.
level = [1] * (n + 1)
for u in order:
for v in adj[u]:
level[v] = max(level[v], level[u] + 1)
print(max(level[1:]))오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번 사전순 순서, 2번 순서가 유일한지(1번과 같은 입력이라냥), 3번 사이클 판별, 4번 완료 시간, 5번 최소 단계라냥.
칸 알고리즘 뼈대를 한 번 짜두면 나머지는 훑으면서 무엇을 기록하느냐만 바뀐다냥. 가보자냥~