[JAVA] 백준 (골드5) 14567번 선수과목 (Prerequisite)

링크

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

---

입력 예제

6 4
1 2
1 3
2 5
4 5

---

출력 예제

1 2 2 1 3 1

---

풀이

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 선수과목은 사이클이 없고 방향이 정해져 있다. 그리고 각 과목의 이수 학기는 순서를 정하는 것과 같은 것이므로 위상 정렬로 해결할 수 있다.

위상 정렬은 진입 차수란 개념을 알아야 하는데, 진입 차수는 자기 자신을 가리키는 에지의 개수에 해당한다. 예제의 경우 각 에지는 다음과 같고

1 -> 2
1 -> 3
2 -> 5
4 -> 5

진입 차수는 다음과 같다.

[0, 1, 1, 0, 2, 0]

위상 정렬은 진입 차수가 0인 노드부터 인접 노드를 탐색하여 진입 차수를 감소시키고 0이 되면 해당 노드들 부터 다시 탐색하여 모든 노드가 정렬될 때 까지 반복한다.

while (!queue.isEmpty()) {
    Integer cur = queue.poll();
    
    for (Integer next : adjList.get(cur)) {  //인접 노드 탐색
        inDegree[next]--;  //진입 차수 -1
        
        if (inDegree[next] == 0) {  //진입 차수가 0이면 큐에 추가
            queue.add(next);
            result[next] = result[cur] + 1;
        }
    }
}

전체 코드

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

/*
백준 / 선수과목 / 골드5
https://www.acmicpc.net/problem/14567
 */
public class Main {

    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[] result = new int[N + 1];
        int[] inDegree = new int[N + 1];
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.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());
            adjList.get(A).add(B);
            inDegree[B]++;  //진입 차수 계산
        }

        Queue<Integer> queue = new LinkedList<>();
        //진입 차수가 0인 노드를 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
                result[i] = 1;
            }
        }

        while (!queue.isEmpty()) {
            Integer cur = queue.poll();

            for (Integer next : adjList.get(cur)) {  //인접 노드 탐색
                inDegree[next]--;  //진입 차수 -1

                if (inDegree[next] == 0) {  //진입 차수가 0이면 큐에 추가
                    queue.add(next);
                    result[next] = result[cur] + 1;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(result[i]).append(" ");
        }

        System.out.println(sb);
    }
}