[JAVA] 백준 1766 문제집

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

1766번: 문제집

풀이 후기

- 처음에 dfs로 풀이하려 했더니 해결 전략에 있는 반례가 존재했다

- 그림을 그려보니 진입 차수가 0인 노드들에 대해 우선순위로 뽑으며 순서를 정하면 되겠다 싶어서 정석 위상 정렬 풀이로 바꿨다

 

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        
        ArrayList<Integer>[] graph = new ArrayList[N+1];
        int[] degree = new int[N+1];
        for(int i=1;i<=N;i++) graph[i] = 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());
            graph[a].add(b);
            degree[b]++;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=1;i<=N;i++){
            if(degree[i]==0) pq.add(i);
        }

        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            int cur = pq.poll();
            sb.append(cur).append(' ');

            for(int i=0;i<graph[cur].size();i++){
                int next = graph[cur].get(i);
                
                degree[next]--;
                if(degree[next]==0) pq.add(next);
            }
        }

        System.out.println(sb);
    }

}