[백준 1766번] 문제집 :: 늦깎이 IT

[백준 1766번] 문제집 URL

1. 이 문제는 단순 위상정렬과 거의 같지만, 방문 순서에 따른 제약조건이 존재한다.

2. 진입차수가 0인 노드들을 먼저 탐색하기 시작할 때, 그 노드들을 오름차순으로 방문한다.

3. 이를 위해서 최소 힙을 사용했다. 최소 힙을 사용하게 되면 자동으로 숫자가 낮은 노드먼저 방문할 수 있다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static List<Integer>[] list;
    static int[] indegree;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        indegree = new int[N + 1];
        list = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++)
            list[i] = new ArrayList<Integer>();
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int st1 = Integer.parseInt(st.nextToken());
            int st2 = Integer.parseInt(st.nextToken());
            list[st1].add(st2);
            indegree[st2] += 1;
        }
        topologySort();
 
    }
 
    public static void topologySort() {
 
        Comparator<Integer> minHeap = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        };
        PriorityQueue<Integer> q = new PriorityQueue<>(minHeap);
        List<Integer> result = new ArrayList<>();
 
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0)
                q.offer(i);
        }
 
        for (int i = 1; i <= N; i++) {
 
            if (q.isEmpty()) {
                System.out.println("사이클 발생");
                return;
            }
 
            int node = q.poll();
            result.add(node);
 
            for (int j = 0; j < list[node].size(); j++) {
 
                int adj = list[node].get(j);
                indegree[adj] -= 1;
 
                if (indegree[adj] == 0)
                    q.offer(adj);
            }
        }
 
        for (int v : result)
            System.out.print(v + " ");
    }
}