위상정렬 알고리즘 (BOJ_14567 선수과목)

문제상황

여러가지 수업을 듣는다고 가정하자.
각 수업을 수강하기위해서는 먼저 공부해야하는 선수과목들이 존재한다고 할 때, 즉 수강해야하는 과목의 순서가 있다고 할 때 수강할 수 있는 과목의 순서는?
이러한 선후관계가 존재할 때, 순서를 찾아야 한다면 위상 정렬을 사용할 수 있다.
또한, 모든 노드들이 선후관계가 정해져 있지 않을 수 있으므로 여러 가지가 존재할 수 있다.
주의 ) 위상정렬을 사용하기 위해서는 그래프가 순환하지 않아야한다.

위상정렬이란?

• 유향 그래프의 정점들을 변의 반향을 거스르지 않도록 나열하는 것을 의미한다.
• 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다.
• 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 이용할 수 있다.
• 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(Directed Acyclic Graph)여야 한다.

결과

• 위상 정렬이 가능하다? -> 사이클 발생 여부 확인 가능
• 가능하다면 정렬된 결과

구현방법

• BFS (큐)
• DFS (재귀)

BFS

1. 그래프의 각 노드들의 진입 차수 테이블 생성 및 진입 차수 계산
2. 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다.
3. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선을 제거한다.
   -> 인접한 노드의 진입 차수를 1 감소시킨다.
4. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
5. 큐가 빌 때까지 3-4을 반복한다.
   -> 모든 노드 처리 시 위상정렬 ok.
   -> 모든 노드 처리되지 않는다면 사이클 발생

위상 정렬을 BFS로 구현 with Java (BOJ14567 선수과목)

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

package blog;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

// BOJ 14567 선수과목
public class TopologicalSort {

    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());

        // 진입차수
        int[] edgeCount = new int[N+1];

        // 그래프
        ArrayList<ArrayList<Integer>> edgeList = new ArrayList<>();
        for (int i = 0; i <= N; i++) edgeList.add(new ArrayList<>());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            edgeList.get(A).add(B);
            edgeCount[B]++;
        }
        // 선수과목번호
        Queue<int[]> q = new ArrayDeque<>();
        int[] ans = new int[N+1];
        for (int i = 1; i <= N; i++) {
            if (edgeCount[i] == 0) q.offer(new int[] {i, 1});
        }
        while (!q.isEmpty()) {
            int[] from = q.poll();
            int A = from[0];
            ans[A] = from[1];
            for (int i = 0; i < edgeList.get(A).size(); i++) {
                int to = edgeList.get(A).get(i);
                edgeCount[to]--;
                if (edgeCount[to] == 0) q.offer(new int[] {to, ans[A] + 1});
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 1; i <= N; i++) bw.write(String.valueOf(ans[i]) + " ");
        bw.flush();
        br.close();
    }
}