초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
졸업까지 들을 과목의 순서를 짜 주는 프로그램을 만든다고 합시다. 자료구조를 들어야 알고리즘을 들을 수 있는 것처럼 먼저 들어야 하는 과목이 정해져 있고, 이런 조건이 수십 개 얽혀 있습니다. 조건을 모두 지키는 순서는 어떻게 찾을까요?
“A를 B보다 먼저 한다”를 A에서 B로 가는 간선으로 그리면 방향 그래프입니다. 모든 간선이 앞에서 뒤로 향하도록 정점을 한 줄로 세우는 것을 위상 정렬(topological sort)이라 합니다. 양말을 신어야 신발을 신을 수 있는 옷 입기로 해 봅시다.
옷을 눌러 입어 봅시다.
화살표가 들어오는 옷은 화살표가 시작하는 옷을 먼저 입어야 합니다.
답은 하나가 아닙니다. 시계는 아무 때나 차도 되고, 속옷과 셔츠는 어느 쪽을 먼저 입어도 됩니다.
지금 입을 수 있는 옷은 아직 안 입은 옷에서 오는 화살표가 없는 옷입니다. 정점으로 들어오는 간선의 수를 진입 차수(in-degree)라 합니다. 입은 옷의 화살표를 지워 가면, 진입 차수가 0인 정점이 곧 지금 할 수 있는 일입니다.
이 방법을 칸 알고리즘(Kahn’s algorithm)이라 합니다. 정점마다 한 번 꺼내고 간선마다 한 번 지우니, 정점이 V개, 간선이 E개면 O(V + E)입니다.
진입 차수가 0인 속옷, 셔츠, 양말, 시계를 큐에 넣었습니다.
정점 위 숫자가 남은 진입 차수입니다. 끝까지 진행한 뒤 “재킷 → 셔츠 간선 더하기”를 켜고 다시 해 봅시다.
위 네 단계를 C로 옮겨 봅시다.
출력 없음재생하며 queue와 indegree가 바뀌는 모습을 봅시다.
재킷 → 셔츠 간선을 더하면 셔츠는 재킷을, 재킷은 넥타이를, 넥타이는 셔츠를 기다립니다. 이처럼 화살표를 따라가다 출발한 정점으로 돌아오는 길을 사이클(cycle)이라 합니다. 사이클 위의 정점은 어느 것도 맨 먼저 세울 수 없으니, 사이클이 있으면 위상 정렬은 불가능합니다.
칸 알고리즘은 이것도 알려 줍니다. 사이클 위 정점과 그 뒤에 올 정점은 진입 차수가 0이 되지 않아 큐에 들어가지 못합니다. 끝났을 때 줄에 선 정점이 V개보다 적으면 사이클이 있습니다.
과목 A부터 H까지 8개를 한 학기에 하나씩 듣습니다. 아래는 '왼쪽 과목을 먼저 들어야 오른쪽 과목을 들을 수 있다'는 조건입니다. H는 아무 조건이 없습니다. 조건을 모두 지키는 수강 순서는 몇 가지일까요? 숫자로 답하세요.
A → B, B → C, C → G D → E, E → F, F → G