[Baekjoon] 백준 14567번: 선수과목 (JAVA)

문제 14567

14567번: 선수과목 (Prerequisite)

[ 풀이 과정 ]

대표적인 위상 정렬 문제입니다. 위상정렬 문제는 아래의 내용을 기본으로 해서 풉니다.
1. 방향 그래프를 만든다. (연결 리스트 생성)
2. 각 노드의 진입차수를 배열로 저장한다.
3. 진입차수가 0인 노드를 그래프에서 하나씩 지워가며 queue에 저장한다.

학기는 depth로 생각할 수 있으므로, 큐의 현재 사이즈만큼 돈 후에 하나씩 증가시켜주면 됩니다. 문제에 나와있는 예제 입력 2를 보면 아래와 같습니다.

방향 그래프

진입차수 배열

 

진입차수가 0인 노드 1, 4, 6을 먼저 queue에 넣은 다음, 큐의 사이즈 3만큼 반복하여 노드를 하나씩 제거하여 노드와 연결되어 있는 노드의 진입차수를 하나씩 빼면 됩니다. 위의 그림에서 1의 노드를 제거한 후의 모습은 아래와 같습니다.

방향 그래프

변경된 진입차수

 

[ 코드 ]

import java.io.*;
import java.util.*;

public class Main {
    private static ArrayList<Integer>[] subjects;
    private static int[] inDegree; // 진입차수
    private static final Queue<Integer> queue = new LinkedList<>();
    private static int[] res;

    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 M = Integer.parseInt(st.nextToken());
        subjects = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            subjects[i] = new ArrayList<>();
        }
        inDegree = new int[N+1];
        res = new int[N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            subjects[parent].add(child);
            inDegree[child]++; // 진입차수 증가
        }

        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        topologySort();
        for (int n: res) {
            bw.write(n + " ");
        }
        bw.flush();
    }

    private static void topologySort() {
        int semester = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                int cur = queue.poll();
                res[cur-1] = semester;
                for (int next: subjects[cur]) {
                    inDegree[next]--;
                    if (inDegree[next] == 0) queue.offer(next);
                }
            }
            semester++;
        }
    }
}