[백준] 1766번 문제집

[CMSSKKK]

TITLE

문제집

위상정렬

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

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

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());
        List<List<Integer>> problems = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            problems.add(new ArrayList<>());
        }
        int[] check = new int[n+1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int p1 = Integer.parseInt(st.nextToken());
            int p2 = Integer.parseInt(st.nextToken());

            problems.get(p1).add(p2);
            check[p2]++;
        }
        System.out.println(sort(problems, check));
    }

    private static String sort(List<List<Integer>> list, int[] check) {

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < list.size(); i++) {
            if (check[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer num = queue.poll();
            sb.append(num).append(" ");

            for (int p : list.get(num)) {
                check[p]--;
                if(check[p] == 0) {
                  queue.offer(p);
                }
            }
        }
        return sb.toString();
    }
}

핵심 로직 혹은 자료구조

• 위상정렬
• 우선순위 큐 사용

시간 복잡도

• O( )