위상 정렬 / BOJ 2252번 줄세우기

정의

유향 그래프의 정점을 간선의 방향에 거스르지 않도록 나열하는 것

• ex) 대학 선수 과목: 특정 과목들을 수강해야 할 때 선수 과목이 있다면 위상 정렬을 통해 올바른 수강 순서를 찾을 수 있음

모든 유한 부분 순서 집합은 유향 그래프 G = (V,E)로 나타낼 수 있으므로,

해당 그래프의 모든 간선 e = (u,v)에 대해 u가 v보다 앞에 위치하도록 만드는 과정을 위상 정렬이라고 한다.

단, 유향 그래프 G는 DAG(유향 비순환 그래프)일 때만 위상 정렬이 성립한다.

 

사이클이 있는 그래프는 진입 차수가 0이 될 수 없기 때문에 위상 정렬이 불가능하다.

 

알고리즘

위상 정렬은 꼭지점의 양수 노드의 선형 실행 시간을 갖는다

O(|V| + |E|)

 

Kahn 알고리즘

1. 모든 정점의 진입 차수를 계산한다.
   • 그래프 입력 시, 간선(u-> v)에 대해 v의 진입 차수를 +1 한다.
2. 진입 차수가 0인 모든 정점을 큐에 넣는다.
3. 큐가 빌 때까지 아래 행동을 반복한다.
   • 큐에서 정점을 꺼낸다.
     • 이 때, 꺼낸 순서가 위상 정렬의 순서
   • 해당 정점의 모든 인접 정점에 대해 진입 차수를 1씩 감소한다.
   • 만약 감소한 인접 정점이 0이 된 경우, 큐에 해당 정점을 넣는다.
4. 모든 정점 처리 완료 -> 위상 정렬 완료

위 과정으로 정점을 모두 꺼내지 못했다면 그래프에 사이클이 존재함

 

예시

다음과 같은 DAG가 있다고 가정해보자.

 

---

1) 초기 진입 차수 계산

정점진입 차수(in-degree)

A	0
B	1 (A→B)
C	1 (A→C)
D	2 (B→D, C→D)

진입 차수 0 → A

초기 큐: [A]

---

2) Kahn 알고리즘 단계별 실행

 

단계 1 — A 꺼내서 처리

• A 출력 → 위상 정렬 결과: A
• A의 인접 정점 B, C의 진입 차수 감소

정점진입 차수 변화

B	1 → 0
C	1 → 0
D	2

큐에 B, C 추가
현재 큐: [B, C]

---

단계 2 — B 꺼내서 처리

• B 출력 → 결과: A, B
• B → D의 진입 차수 감소

정점진입 차수 변화

D

2 → 1

큐: [C]

---

단계 3 — C 꺼내서 처리

• C 출력 → 결과: A, B, C
• C → D의 진입 차수 감소

정점진입 차수 변화

D

1 → 0

D의 진입 차수가 0이 되었으므로 큐에 삽입
큐: [D]

---

단계 4 — D 꺼내서 처리

• D 출력 → 결과: A, B, C, D
• 후속 정점 없음

큐: []

---

최종 위상 정렬 결과

 

A → B → C → D

(또는 B와 C 순서는 바뀔 수 있음
즉, A → C → B → D도 가능)

 

전체 과정

초기	[A]	-	-	-
1	[A]	A	B:1→0, C:1→0	A
2	[B,C]	B	D:2→1	A,B
3	[C]	C	D:1→0	A,B,C
4	[D]	D	-	A,B,C,D

 

관련 문제

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

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_2252 {
    public static void main(String[] args) throws IOException{
        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());
        int[] degree = new int[N+1];

        ArrayList<Integer>[] adjList = new ArrayList[N+1];
        for (int i = 0; i < adjList.length; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            adjList[v].add(e);
            degree[e]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if(degree[i]==0){
                queue.offer(i);
            }
        }

        StringBuilder sb = new StringBuilder();

        while(!queue.isEmpty()){
            int cur = queue.poll();
            sb.append(cur).append(" ");

            for (int next : adjList[cur]) {
                degree[next]--;
                if(degree[next] == 0){
                    queue.offer(next);
                }
            }
        }
        
        System.out.println(sb.toString());
    }
}