[JAVA] 백준, 1766번 문제집

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

 

문제 풀이

문제 조건 중에 2가지를 가져온 것인데, 여기서 위상 정렬을 사용해야겠다고 생각을 했다. 원래라면 번호가 낮은 문제가 쉽기 때문에 먼저 풀어야겠으나, 1번 조건에서 먼저 푸는 것이 좋은 문제가 있다면 해당 문제를 풀어야 한다고 한다.

1. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
2. 가능하면 쉬운 문제부터 풀어야 한다.

1 ~ 4번까지 4개의 문제가 있을 때, 원래라면 1 -> 2 -> 3 -> 4 순서대로 풀어야 풀기 쉽지만, 2번을 먼저 풀어야 1번을 쉽게 풀 수 있다는 조건이 걸린 것이다. 마치 2번에서 사용된 개념을 이용하여 1번을 풀 수 있는 느낌이다.

 

또한 우선순위 큐를 사용해야 하는데, 그 이유는 2번 조건 때문에 쉬운 문제부터 풀어야하기 때문이다. 

 

코드

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

public class Main {

    static int N, M;
    static int[] inDegree;
    static PriorityQueue<Integer> que = new PriorityQueue<>();
    static List<List<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        inDegree = new int[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph.get(u).add(v);
            inDegree[v]++;
        }

        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                que.offer(i);
            }
        }

        while (!que.isEmpty()) {
            int first = que.poll();
            sb.append(first + " ");

            for (int second : graph.get(first)) {
                inDegree[second]--;
                if (inDegree[second] == 0) {
                    que.offer(second);
                }
            }
        }

        System.out.println(sb);
    }
}