위상 정렬
위상 정렬(Topological Sort)는 순서가 정해져 있는 유향 그래프의 정점을 간선의 방향을 거스르지 않도록 나열하는 것을 의미합니다. 유향 그래프의 예시와 위상 정렬 방법을 통해 진행하도록 하겠습니다.
우선 다음과 같은 그래프에 대해서 위상 정렬을 진행한다고 가정해보겠습니다. 이러한 흐름은 마치 조건과 같이 생각할 수 있습니다. 마치 대학교에서 선수 과목에 해당하는 것과 비슷하다고 할 수 있겠습니다. 위 그래프의 경우 정점 4는 정점 1과 정점 3을 기본적으로 방문해야 방문이 가능합니다.
이 조건을 생각하며 정렬을 하면 1 - 2 - 3 - 4 - 5가 될 수 있습니다. 하지만, 경우에 따라 이 정렬이 여러 케이스가 나올 수 있습니다. 여러 케이스의 경우에는 조건에 따른 우선순위에 따라 결정을 하면 됩니다.
중요한 조건으로는 그래프가 반드시 DAG(Directed Acyclic Graph), 즉 사이클이 없는 유향그래프인 경우에만 위상 정렬이 가능합니다.
방법
다시 이 그래프를 보면서 위상 정렬을 하는 방법을 알아보겠습니다. 스택과 큐를 이용하는 방법 두 가지가 알려져있는데, 여기서는 큐를 사용하도록 하겠습니다.
큐를 사용하기 전, 위상 정렬의 시작점이 필요합니다. 바로 자신에게로 들어오는 간선의 수, 즉 진입차수를 먼저 구해야됩니다. 각각의 진입차수는 아래와 같습니다.
| 정점 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 진입 차수 | 0 | 1 | 1 | 2 | 1 |
여기서 시작점은 진입차수가 0인 부분입니다. BFS를 하듯 방문할 정점들을 큐에 담아줍니다.
그리고 아래 과정을 큐가 완전히 빌 때까지 반복합니다.
- 큐에서 하나를 빼서 이어진 정점들의 진입차수를 하나씩 줄여줍니다.
- 이어진 정점에 대해서
- 진입차수가 0인 경우에는 큐에 담아줍니다.
- 진입차수가 0보다 큰 경우에는 그냥 무시해줍니다.
예를 들어 정점 1을 큐에 넣고 뺄 경우 2번과 4번이 이어진 정점이라 둘의 진입차수를 1씩 빼줍니다.
- 정점 2의 경우 진입차수가 0가 되게 되어 큐에 담으면 됩니다.
- 정점 4의 경우 진입차수가 1이기에 0보다 큽니다. 그냥 무시해줍니다.
문제
BOJ 14567
https://www.acmicpc.net/problem/14567
물론 위상 정렬이 아닌 다른 방법으로도 풀이가 가능한 문제이지만, 가장 기본적인 위상정렬 문제인만큼 위상 정렬로 풀이하겠습니다.
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int time;
int prev; // 진입차수
List<Integer> next;
Node() {
this.time = 0;
this.prev = 0;
this.next = new ArrayList<>();
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Queue<Integer> q = new LinkedList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Node[] nodes = new Node[N + 1];
for(int i = 1; i <= N; i++) {
nodes[i] = new Node();
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
nodes[A].next.add(B);
nodes[B].prev++;
}
for(int i = 1; i <= N; i++) {
if(nodes[i].prev == 0) {
nodes[i].time = 1;
q.offer(i);
}
}
while(!q.isEmpty()) {
int now = q.poll();
for(int next : nodes[now].next) {
if(nodes[next].time > 0) continue; // 방문을 했던 점은 0보다 크다
if(--nodes[next].prev > 0) continue;
nodes[next].time = nodes[now].time + 1;
q.offer(next);
}
}
for(int i = 1; i <= N; i++) {
sb.append(nodes[i].time).append(" ");
}
System.out.println(sb.toString());
br.close();
}
}BOJ 1766
https://www.acmicpc.net/problem/1766
조금 더 정렬 조건이 주어진 위상 정렬 문제입니다. 정점의 번호(난이도)가 곧 우선순위의 기준이 되기에, 일반적인 큐 대신 우선순위 큐를 활용하여 위상 정렬을 수행합니다.
import java.io.*;
import java.util.*;
public class Main {
static class Problem implements Comparable<Problem>{
int num;
boolean visited;
LinkedList<Problem> list;
Problem(int num, int n) {
this.num = num;
this.visited = false;
this.list = new LinkedList<>();
}
@Override
public int compareTo(Problem p) {
return this.num - p.num;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nm = br.readLine().split(" ");
StringBuilder sb = new StringBuilder();
PriorityQueue<Problem> pq = new PriorityQueue<>();
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[] before = new int[n + 1];
Problem[] nodes = new Problem[n + 1];
for(int i = 1; i <= n; i++) {
nodes[i] = new Problem(i, n);
}
for(int i = 0; i < m; i++) {
String[] ab = br.readLine().split(" ");
int a = Integer.parseInt(ab[0]);
int b = Integer.parseInt(ab[1]);
before[b]++;
nodes[a].list.add(nodes[b]);
}
for(int i = 1; i <= n; i++) {
if(before[i] == 0) {
pq.add(nodes[i]);
nodes[i].visited = true;
}
}
while(!pq.isEmpty()) {
Problem now = pq.remove();
sb.append(now.num).append(" ");
for(Problem next : now.list) {
if(next.visited) continue;
if(--before[next.num] != 0) continue;
pq.add(next);
next.visited = true;
}
}
System.out.println(sb.toString());
br.close();
}
}