해당 포스팅은, 백준 2252 줄세우기 문제를 활용하여 설명됩니다.

위상 정렬 알고리즘

위상 정렬이란?

위상 정렬은 방향 그래프(Directed Graph)에서 의존 관계를 위반하지 않도록 정점들을 순서대로 나열하는 정렬 방법입니다.

“선행 작업이 끝나야 다음 작업을 할 수 있다”와 같은 제약이 있을 때 가능한 실행 순서를 도출하는 데 사용합니다.

위상 정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph) 에서만 유효합니다.

사이클이 존재하면 서로가 서로를 선행 조건으로 요구하는 상태가 발생하여 올바른 순서를 만들 수 없습니다.

위상 정렬이 필요한 경우

위상 정렬은 생각보다 다양한 경우에 유용하게 활용 될 수 있습니다.

만약 선수 과목이 존재하는 교육 시스템을 개발한다고 생각 해보겠습니다.

다양한 과목이 있고, 특정한 과목을 수강 하기 위해서는 선수 과목이 있다고 가정합니다.

체크 표시되어있는 곳이, 학습 완료한 과목이라고 가정합니다.
~~위 순서는 그냥 막 적은 것 입니다. 로드맵 아니에요~~

여기서, 저는, ORM을 학습하고 싶어 수강 신청을 하려고 합니다.

하지만, 이때 데이터 베이스 기초를 학습하지 않은 상태이기 때문에, ORM은 수강할 수 없습니다.

즉, 처음 설명한 "선행 작업이 끝나야 다음 작업을 진행할 수 있는" 대표적인 예시로 볼 수 있습니다.

만약, 위 그래프가 주어질 때, 유효한 학습 수강 시나리오를 작성하는 요구사항이 있다면, 위상정렬은 매우 요긴하게 사용됩니다.

알고리즘 알아보기

위상 정렬을 위해서는 반드시 알아야 하는 개념이 몇가지 존재합니다.

혹시 그래프에 대한 정보가 필요하다면?그래프 자료구조를 참고하시기 바랍니다!

문제 분석

백준 줄 세우기를 통해 알고리즘을 알아보겠습니다.

내용은 복잡하지 않고, N명의 학생들을 키 순서대로 정렬해 출력하는 것 입니다.

키 정보는 주어지지 않고, 마치 스무고개 하듯 "A는 B보단 커" 라고 주어집니다.

따라서, 다양한 조합의 정답이 파생됩니다.

각 예제들을 그래프로 표현하면 다음과 같이 표현할 수 있습니다.

예제1)

예제2)

예제1의 답은 사이트에는 1->2->3 으로 나와 있으나, 사실 2->1->3 또한 문제 없이 정답입니다.

2번 학생과 1번 학생의 키차이에 대한 정보는 나오지 않기 떄문입니다.

예제 2또한, 살펴보면 정말 다양한 정답이 나올 수 있습니다.

직접 머리속으로 풀어보기

입력으로 주어진 그래프를 그렸다면, 먼저 나와도 상관없는, 즉 남아있는 사람 중 나보다 키가 더 큰 사람이 없는 사람을 골라야 합니다.

예제2를 기준으로 보면 4번과 3번이 이에 해당됩니다.

즉, 둘 중 아무나 먼저 세워도 전혀 상관이 없습니다.

그냥 4번을 먼저 세워주도록 하겠습니다.

다음으로 후보군을 살펴봅니다.

2번과 3번 모두, 선행 조건 (더 큰사람이 있는가? 없다!)를 만족하여 누구든 먼저 나올 수 있는 상태입니다.

3번을 먼저 세워주도록 하겠습니다.

다음 후보군은 자연스럽게 2, 1이 되고, 누가 오든 상관이 없어집니다.

따라서, 정답은 4->3->2->1 이 될 수 있습니다.

하지만 생각하기에 따라(우선순위) 4->2->3->1, 4->3->1->2 등 여러가지 경우가 모두 정답이 될 것 입니다.

머리속 생각을 그래프로 생각하기

위에서 후보군을 몇가지 지정하면서 "먼저 누가 올것인가?" 를 확인하였습니다.

그래프적인 특징으로 살펴본다면 후보군들은 항상, indegree 가 0인 정점입니다.

Indegree? 모른다면? 참고할 만한 블로그

따라서 상황이 진행됨에 따라 Indegree 가 0인 정점 들을 찾고, 줄을 세웠다면 관련 있는 간선과 정점을 제거해 나간다면 해결이 가능한 문제 입니다.

다만, 적절하게 자료구조를 선택하지 않는다면, 분명 N^2의 시간복잡도를 가지게 될 것 입니다.

왜?
모두 배열이나 인접 리스트에 저장해뒀다면, Indegree 가 0인 정점을 찾기 위해서 N만큼 반복하며 찾을 것 이고, 그 행위를 정점만큼 또 반복할 것이기 때문에, N^2이 걸릴 가능성이 높습니다.

따라서, 현재 각 정점들의 Indegree 를 저장하는 배열과, Indegree 가 0인 정점들만 모아두는 큐를 통해 이 문제를 해결해나갑니다.

물론! 구현에 따라 다릅니다.
Queue가 아니라, Stack이나 PQ 등을 사용해도 됩니다.
모든 내용은 문제 조건에 따라 달라집니다!

위상 정렬 핵심 요약

이 알고리즘을 해결하는 중요한 핵심은 다음과 같습니다.

indegree가 0인 정점은 언제든지 먼저 선택할 수 있다
정점을 선택하면, 그 정점이 향하던 간선들은 제거된다
간선 제거로 인해 새롭게 indegree가 0이 된 정점이 다음 후보가 된다
이를 반복하면 의존 관계를 만족하는 하나의 순서를 얻을 수 있다

위상 정렬의 시간 복잡도

각 정점은 큐에 한 번 들어간다
각 간선은 indegree 감소 과정에서 한 번만 처리된다

두가지로 인해, 전체 시간 복잡도는, O(N + M) 으로 처리가 가능합니다.

문제 해결하기

코드 흐름

코드 흐름은 다음과 같이 진행됩니다.

입력을 통해 그래프를 구성한다.
A B → A가 B보다 앞에 서야 한다 → A → B
각 정점의 indegree를 계산한다.
indegree가 0인 정점을 큐에 넣는다.
큐에서 정점을 하나 꺼내 결과에 추가한다.
해당 정점이 가리키는 모든 정점의 indegree를 감소시킨다.
새롭게 indegree가 0이 된 정점을 큐에 넣는다.
큐가 빌 때까지 반복한다

전반적으로 BFS 향이 조금 첨가되어 있다고 생각하면 조금 편하게 이해할 수 있습니다.

전체 코드

코드보단 위의 내용을 이해 하는게 더 중요합니다.

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 학생 수
		int M = Integer.parseInt(st.nextToken()); // 비교 횟수

		List<List<Integer>> effectList = new ArrayList<>(); //각 정점이 어떤 정점들에게 영향을 끼쳤는지 확인하기 위한 리스트
		for (int i = 0; i <= N; i++) {
			effectList.add(new ArrayList<>());
		}

		int[] ingress = new int[N + 1]; //각 정점이 result 에 저장되기 전에, 먼저 처리되어야 하는 정점의 개수

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			// 학생 A가 B 앞에 있어야함.
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			ingress[B]++; // B 정점은, 누군진 몰라도, 앞에 정점 하나가 먼저 처리되어야 등장이 가능
			effectList.get(A).add(B); // A 정점은, B 정점에게 영향을 끼쳤다.
		}

		// ingress[Node] 의 값이 0인 친구들을 넣을 곳
		// 즉, q에는 현재 언제 나와도 상관없는 정점들의 큐
		Queue<Integer> q = new LinkedList<>();
		insertZeroIngressNode(ingress, q);

		StringBuilder sb= new StringBuilder();

		while(!q.isEmpty()) {
			Integer nowNode = q.poll();
			sb.append(nowNode).append(" ");

			for (int effectedNode : effectList.get(nowNode)) {
				ingress[effectedNode]--;

				if(ingress[effectedNode] == 0) {
					q.add(effectedNode);
				}
			}
		}

		System.out.println(sb.toString());
	}

	private static void insertZeroIngressNode(int[] ingress, Queue<Integer> q) {
		for(int i=1; i<ingress.length; i++){
			if(ingress[i] == 0) {
				q.add(i);
				ingress[i]--;
			}
		}
	}
}

발전해보기 1

만약, 문제가 조금더 복잡하게 다음과 같은 규칙이 추가 되었다고 가정하겠습니다.

"만약 순서가 동일하다면 더 낮은 번호를 가지고 있는 사람을 우선적으로 줄 세웁니다."

그렇게 된다면, Queue 가 아닌, PQ 를 통해 처리하면 됩니다.

현재 큐에는, 언제든지 먼저 줄에 설 수 있는 Indegree 가 0인 정점들만 모아져 있는 상태입니다.

따라서, PQ 를 통해 정점 간의 순서를 정렬해서 사용할 수 있다면 위의 추가 조건을 만족할 수 있게 됩니다.

발전해보기 2

처음에 DAG 일때만 가능한 알고리즘이라고 하였습니다.

만약 순환 사이클이 있다면 어떤 현상이 발생할까요?

A->B

B->C

C->A

에서, 모두가 먼저 나가 줄을 서든 한가지 정보는 거짓이 되어서 모순이 발생하게 됩니다.

이 경우에는 올바른 줄 세우기는 존재하지 않게 됩니다.

~~지금 생각해보니, 하나 틀린거 적어놓고 그걸 찾게하는 문제를 만들면 재밌겠네요~~

위상 정렬(Topology Sort) 알고리즘