15. 위상정렬 (Topological Sorting)

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미합니다. 

위상정렬 - 위키백과

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

정의를 보아서는 쉽게 와닫지 않을듯하여 예시를 들어 설명하도록 하겠습니다. 스타크래프트를 플레이한다고 가정해보겠습니다. 게임에서 승리하기 위해서는 유닛을 생산하고 상대방을 공격하여 상대방의 모든 건물을 부숴야합니다. 유닛을 생산할 때에 더 높은 파워를 가진 고급 유닛을 생산하기 위해서는 고급 유닛을 생산할 수 있는 건물을 지어야하는데 단순히 원한다고 지을 수가 있는게 아니라 사전에 지어야하는 여러 건물들이 있습니다. 기초 건물들이 모두 완성되어야 다음 건물을 지을 수 있는 것입니다. 이와같이 건물들이 건설되는 순서를 정해주기 위해서 위상정렬을 사용합니다.

위상정렬은 구현방식은 비교적 간단합니다. 입력되는 연결관계를 저장해줍니다. 이때 단순하게 연결관계를 저장하는데서 그치는 것이 아니라 노드 숫자만큼 배열을 하나 선언한 뒤, 입력되는 간선 정보에서 노드가 도착지에 해당할 경우 그 노드가 다른 노드에서 들어오는 간선을 갖고 있다는 의미에서 하나씩 값을 더해줍니다. 마지막까지 간선정보가 입력되고 나면 노드간 연결 순서는 알 수 없지만 적어도 어떤 방향으로 서로 연결되었는지 연결정보와 노드들이 해당 노드로 들어올 수 있는 간선을 몇 개 갖고 있는지 정보를 갖게 됩니다. 이 상태에서 자신으로 들어오는 간선이 없는 노드가 시작노드가 됩니다. 이 노드들을 Queue에 저장해주고 Queue가 비었는지를 확인하는 조건으로 while문이 돌게 됩니다. Queue에서 하나의 노드를 뽑고 이 노드에 순서를 부여하고 그 노드와 연결된 모든 노드들을 돌면서 하나씩 간선 정보를 덜어줍니다. 한마디로 이미 순서가 확인된 노드와 다른 노드들의 관계를 끊어주는 것입니다. 만일 그렇게 간선정보가 하나 줄었을 때 더이상 연결된 간선이 없는 것으로 나온다면 그 노드의 순서에 다른 노드들이 더 이상 관여할 수 없다는 것을 의미하므로 Queue에다 추가해줍니다. 하지만 연결된 간선이 여전히 있는 것으로 나온다면 다른 노드들이 끊어진 이후에야 그래프에서 자신의 순서를 알 수 있다는 것을 의미합니다.

위상정렬의 대표적 문제인 줄 세우기 문제를 풀면서 직접 구현해보도록 하겠습니다.

2252번: 줄 세우기

https://www.acmicpc.net/problem/2252

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
	private static int[] in;
	private static ArrayList<Integer> order;
	private static ArrayList<Integer>[] con;
	private static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		st = new StringTokenizer(br.readLine().trim());

		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		con = assignList(con);
		in = new int[N + 1];

		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine().trim());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			con[x].add(y);
			in[y]++;
		}

		Queue<Integer> queue = new LinkedList<Integer>();
		order = new ArrayList<Integer>();
		for (int i = 1; i <= N; i++) {
			if (in[i] == 0)
				queue.add(i);
		}

		while (!queue.isEmpty()) {
			int q = queue.poll();
			order.add(q);
			for (Integer i : con[q]) {
				if (--in[i] == 0)
					queue.add(i);
			}
		}
		for (Integer i : order) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	static ArrayList[] assignList(ArrayList<Integer>[] list) {
		list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		return list;
	}
}