[백준] 1766 문제집 - 자바

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

1766번: 문제집

문제 풀이

그래프로 나타낼 수 있고 그래프의 선후 관계가 존재하므로 위상정렬 알고리즘을 적용하여 쉽게 해결할 수 있다.

하지만 조건이 추가되어 같은 '선'관계끼리는 더 낮은 번호(쉬운 문제)를 먼저 풀어야 한다.

따라서 큐를 통해 문제를 관리하며 더 낮은 값이 들어가도록 우선순위 큐를 사용해주기만 하면 된다.

2252번 문제를 아직 못 풀었다면 먼저 풀어보길 권한다.

 

코드

package 백준;

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

public class b1766 {
    static List<Integer>[] graph;
    static int[] inDegree;
    static StringBuilder sb = new StringBuilder();

    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());

        inDegree = new int[N + 1];
        graph = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph[from].add(to);
            inDegree[to]++;
        }

        topologicalSorting();
    }
    static void topologicalSorting() {
        Queue<Integer> q = new PriorityQueue<>();
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            Integer now = q.poll();
            List<Integer> children = graph[now];
            sb.append(now + " ");

            for (int i = 0; i < children.size(); i++) {
                Integer child = children.get(i);
                inDegree[child]--;

                if (inDegree[child] == 0) {
                    q.offer(child);
                }
            }
        }

        System.out.println(sb);
    }
}