[백준] Q1766 문제집 JAVA

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

1766번: 문제집

1. 문제의 유형 및 이해

위상정렬

N 문제를 풀려고 한다. 각 문제는 난이도 순서로 출제되어 있다 (번호에 따라)

"먼저 푸는 문제" 가 있다는 것을 알게 되었다.
1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제는 먼저 푸는 것이 좋은 문제를 풀어야 한다.
3. 가능하면 쉬운 문제를 풀어야 한다.

풀 문제의 순서를 정해주세요,

 

어떤 정해진 조건에 따라 순서를 정하는 문제입니다.

먼저 풀어야 되는 조건에 따라 선을 연결해주어 그래프 처럼 생각해보면 위상정렬 문제임을 알아차릴 수 있습니다. 

2. 문제 접근 방법

문제에서 주어진 두가지 기준을 생각해봅시다.

- 먼저 푸는 것이 좋은 문제는 먼저 푸는 것이 좋은 문제를 풀어야 한다.

- 가능하면 쉬운 문제를 풀어야 한다.

이 두 가지 정렬기준을 놓고 보았을 때 두 정렬기준의 우선순위를 나눈다면 뭐가 우선이 되어야 할까요.

"가능하면 쉬운 것을 먼저 풀고 싶다" 근데 "먼저 풀 문제가 있따면 먼저 풀겠다" 가 맞는 기준이 됩니다.

 

조금 헷갈린다면, 한 페이지에 하나의 문제가 적혀있는 문제집을 위와 같은 순서로 푼다고 생각해봅시다.

1번 문제를 풀려고 하는 데 추천문제 10번이 적혀있고, 10번으로 갔더니 추천문제 7번이 적혀있습니다.

그럼 우리는 7번 문제를 풀고 10번 문제를 풀고 1번 문제를 풀게 됩니다. 이후에 우리가 풀어야 할 문제는 2번 문제가 됩니다. 

즉, 먼저 풀어야 하는 작은 문제들에 대해서는 위상정렬로 문제를 풀도록 합니다. (inDegree를 사용)

그러한 "가능한 문제"들에 대해 쉬운 것을 먼저 풀 수 있도록 PriorityQueue를 통해 관리해줍니다.

이 문제는 두 가지 정렬 방법에 대해 잘 혼용해서 사용도록 했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    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());
        ArrayList<Integer>[] graph = new ArrayList[N+1];
        int[] inDegree = new int[N+1];
        for (int i = 0; i < N + 1; i++) graph[i] = new ArrayList<>();
        for(int i =0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int prev = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());
            inDegree[target]++;
            graph[prev].add(target);
        }
        PriorityQueue<Integer> problems = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for(int i =1;i<N+1;i++){
            if(inDegree[i] ==0){
                problems.add(i);
            }
        }
        while (!problems.isEmpty()) {
            int cur = problems.poll();
            sb.append(cur).append(' ');
            for (int next : graph[cur]) {
                inDegree[next]--;
                if(inDegree[next] == 0){
                    problems.add(next);
                }
            }
        }
        System.out.println(sb);
    }
}