[JAVA]14567 선수 과목 (위상정렬 입문 추천)

 📚 문제  

14567번: 선수과목 (Prerequisite)

 

🔍 아이디어  

단순한 위상정렬 문제입니다.

위상정렬 - 위키백과, 우리 모두의 백과사전

 

과거에 다른 블로그에 작성한 글입니다.

위상정렬 Topology Sort, 백준 1766 문제집(Java)

 

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj_14567_선수과목 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<List<Integer>> outGraph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            outGraph.add(new ArrayList<>());
        }
        int[] inDegree = new int[n];
        int[] semesters = new int[n];

        while (m-->0){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            outGraph.get(start).add(end); //후수 과목 추가
            inDegree[end]++; //선수 과목이 있는 경우 추가
        }


        //topological sort 위상정렬 과정
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) queue.add(i); 
        }

        int semester = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            semester++;
            for (int i = 0; i < size; i++) {
                int now = queue.poll();
                semesters[now] = semester;
                for (Integer next : outGraph.get(now)) {
                    inDegree[next]--;
                    if (inDegree[next] == 0) queue.add(next);
                }
            }
        }

        //output
        for (int i : semesters) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }
}