[백준] 2252번 줄 세우기

[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.*;

public class Main {
    private static int n;
    private static int m;
    private static List<List<Integer>> nums = new ArrayList<>();
    private static int[] check;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            nums.add(new ArrayList<>());
        }
        check = new int[n+1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            nums.get(num1).add(num2);
            check[num2]++;
        }

        System.out.println(sort());
    }

    private static String sort() {

        Queue<Integer> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if(check[i] == 0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {

           int num = queue.poll();
           sb.append(num).append(" ");

           for (int index : nums.get(num)) {
               check[index]--;
               if(check[index] == 0) {
                    queue.offer(index);
               }
           }

        }
        return sb.toString();
    }


}

핵심 로직 혹은 자료구조

• 위상정렬

시간 복잡도

• O( )