yeolyi.com성열의 컴퓨터공학

위상 정렬

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

졸업까지 들을 과목의 순서를 짜 주는 프로그램을 만든다고 합시다. 자료구조를 들어야 알고리즘을 들을 수 있는 것처럼 먼저 들어야 하는 과목이 정해져 있고, 이런 조건이 수십 개 얽혀 있습니다. 조건을 모두 지키는 순서는 어떻게 찾을까요?

먼저 할 일

“A를 B보다 먼저 한다”를 A에서 B로 가는 간선으로 그리면 방향 그래프입니다. 모든 간선이 앞에서 뒤로 향하도록 정점을 한 줄로 세우는 것을 위상 정렬(topological sort)이라 합니다. 양말을 신어야 신발을 신을 수 있는 옷 입기로 해 봅시다.

속옷셔츠양말바지넥타이벨트신발재킷시계
입은 순서
아직 없음

옷을 눌러 입어 봅시다.

화살표가 들어오는 옷은 화살표가 시작하는 옷을 먼저 입어야 합니다.

답은 하나가 아닙니다. 시계는 아무 때나 차도 되고, 속옷과 셔츠는 어느 쪽을 먼저 입어도 됩니다.

진입 차수

지금 입을 수 있는 옷은 아직 안 입은 옷에서 오는 화살표가 없는 옷입니다. 정점으로 들어오는 간선의 수를 진입 차수(in-degree)라 합니다. 입은 옷의 화살표를 지워 가면, 진입 차수가 0인 정점이 곧 지금 할 수 있는 일입니다.

  1. 진입 차수가 0인 정점을 모두 큐에 넣는다.
  2. 큐에서 정점 하나를 꺼내 줄 끝에 세운다.
  3. 그 정점에서 나가는 간선을 지우고, 그래서 진입 차수가 0이 된 정점을 큐에 넣는다.
  4. 큐가 비면 끝난다. 아니면 2로 돌아간다.

이 방법을 칸 알고리즘(Kahn’s algorithm)이라 합니다. 정점마다 한 번 꺼내고 간선마다 한 번 지우니, 정점이 V개, 간선이 E개면 O(V + E)입니다.

속옷0셔츠0양말0바지1넥타이1벨트2신발2재킷2시계0
큐 (왼쪽이 앞)
속옷셔츠양말시계
줄

진입 차수가 0인 속옷, 셔츠, 양말, 시계를 큐에 넣었습니다.

정점 위 숫자가 남은 진입 차수입니다. 끝까지 진행한 뒤 “재킷 → 셔츠 간선 더하기”를 켜고 다시 해 봅시다.

위 네 단계를 C로 옮겨 봅시다.

1#include <stdio.h>
2
3int main(void) {
4 char *names[9] = {
5 "속옷", "셔츠", "양말",
6 "바지", "넥타이", "벨트",
7 "신발", "재킷", "시계",
8 };
9 // 옷마다 그 옷을 입어야 입을 수 있는 옷
10 int nexts[9][2] = {
11 {3}, {5, 4}, {6},
12 {5, 6}, {7}, {7},
13 {0}, {0}, {0},
14 };
15 int count[9] = {1, 2, 1, 2, 1, 1, 0, 0, 0};
16 int indegree[9] = {0, 0, 0, 1, 1, 2, 2, 2, 0};
17
18 int queue[9];
19 int head = 0;
20 int tail = 0;
21 for (int v = 0; v < 9; v++) {
22 if (indegree[v] == 0) {
23 queue[tail] = v;
24 tail++;
25 }
26 }
27 while (head < tail) {
28 // 큐 앞에서 꺼내 줄 끝에 세운다
29 int v = queue[head];
30 head++;
31 printf("%s\n", names[v]);
32 // v에서 나가는 간선을 지운다
33 for (int i = 0; i < count[v]; i++) {
34 int w = nexts[v][i];
35 indegree[w]--;
36 if (indegree[w] == 0) {
37 queue[tail] = w;
38 tail++;
39 }
40 }
41 }
42 return 0;
43}

변수 없음
출력 없음

재생하며 queue와 indegree가 바뀌는 모습을 봅시다.

사이클

재킷 → 셔츠 간선을 더하면 셔츠는 재킷을, 재킷은 넥타이를, 넥타이는 셔츠를 기다립니다. 이처럼 화살표를 따라가다 출발한 정점으로 돌아오는 길을 사이클(cycle)이라 합니다. 사이클 위의 정점은 어느 것도 맨 먼저 세울 수 없으니, 사이클이 있으면 위상 정렬은 불가능합니다.

칸 알고리즘은 이것도 알려 줍니다. 사이클 위 정점과 그 뒤에 올 정점은 진입 차수가 0이 되지 않아 큐에 들어가지 못합니다. 끝났을 때 줄에 선 정점이 V개보다 적으면 사이클이 있습니다.

도전 문제

과목 A부터 H까지 8개를 한 학기에 하나씩 듣습니다. 아래는 '왼쪽 과목을 먼저 들어야 오른쪽 과목을 들을 수 있다'는 조건입니다. H는 아무 조건이 없습니다. 조건을 모두 지키는 수강 순서는 몇 가지일까요? 숫자로 답하세요.

A → B, B → C, C → G
D → E, E → F, F → G