위상 정렬`

개요

이번 포스팅에서는 위상 정렬에 대해 알아보는 시간을 가지겠습니다.

1. 위상 정렬이란?

위상 정렬이란 순서가 있는 작업들을 수행해야 할 때 사용하는 알고리즘입니다.

순서가 있는 작업은 무엇이 있을까요?

예를 들기 위해 컴퓨터 공학생의 대학 생활을 순서로 정렬해 보겠습니다.

위상 정렬은 DAG (Directed Acyclic Graph), 즉 방향이 있는 비 순환 그래프에만 적용이 가능합니다. (순환이 없으면 사이클도 발생하지 않습니다)

왜 사이클이 발생하면 안되나요?

위상 정렬은 시작점이 존재해야 합니다. 하지만 사이클이 존재하는 그래프에서는 시작점을 찾을 수 없습니다.

또한 졸업 후 다시 대학교 입학 (물론 가능하지만) 으로 돌아갈 수 없습니다.

2. 위상 정렬 구현하기

위상 정렬은 큐를 이용하여 구현 가능합니다.

또한 위상 정렬을 구현하기 위해서는 진입 차수라는 개념이 필요합니다. 예를 들어 위 그림을 통해서 진입 차수를 표현한다면 다음과 같습니다.

정점	대학교 입학	전공 수강	4학년 되기	정보 처리 기사 따기	졸업 하기
진입 차수	0	1	2	3	4

이제 진입 차수가 0인 정점을 큐에 삽입합니다. 위 표에서는 대학교 입학입니다.

큐에서 빼낸 후 연결된 간선을 다 제거해준다면 진입 차수는 새롭게 갱신됩니다.

정점	대학교 입학	전공 수강	4학년 되기	정보 처리 기사 따기	졸업 하기
진입 차수	0	0	1	2	3

다시 진입 차수가 0인 정점을 큐에 삽입합니다. 이번에는 전공 수강이 되겠네요!

그리고 큐에서 제거할 때 갱신도 진행해줍니다.

정점	대학교 입학	전공 수강	4학년 되기	정보 처리 기사 따기	졸업 하기
진입 차수	0	0	0	1	2

이렇게 모든 정점의 진입차수가 0이 될 때 까지 반복해줍니다.

결과적으로 큐에서 꺼내진 순서는 앞서 말했던 대학교 입학, 전공 수강, 4학년 되기, 정보 처리 기사 따기, 졸업하기 순일 것입니다.

3. 예제 문제 실습

2252번: 줄 세우기

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

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

package baekjoon.graph;

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

public class _2252 {

    static int[] in_degree;
    static boolean[] ch;
    static Queue<Integer> queue = new LinkedList<>();
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        in_degree = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }
        // Step 1
        // 모든 정점의 진입 차수를 설정
        // (고민 포인트) 그래프를 입력받고 진입 차수를 어떻게 설정해야 될까?

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            in_degree[b]++;
        }
        
        for (int i = 1; i < in_degree.length; i++) {
            if (in_degree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int temp = queue.poll();

            bw.write(String.valueOf(temp) + " ");
            for (int i = 0; i < graph.get(temp).size(); i++) {
                in_degree[graph.get(temp).get(i)]--;
                if (in_degree[graph.get(temp).get(i)] == 0) {
                    queue.add(graph.get(temp).get(i));
                }
            }
        }
        bw.flush();
    }
}
Java
복사