[백준 - Java] 1766번 : 문제집

문제

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

설명

이 문제는 2623번 음악프로그램과 같이 위상 정렬을 이용하는 문제다.

하지만 문제 조건 중 가능하면 쉬운 문제(번호가 작은 것)부터 풀어야 한다는 조건이 있으므로 Queue 대신 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>[] list = new ArrayList[N + 1];
        int[] indegree = new int[N + 1]; // 진입 차수
		
        for (int i = 0; i < N + 1; i++) {
            list[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());
			
            list[a].add(b);
            indegree[b]++;
        }
		
        // 가능하면 쉬운 문제(번호가 작은 것)부터 풀어야하기 때문에 우선순위 큐를 사용함
        PriorityQueue<Integer> pq = new PriorityQueue<>();
		
        for (int i = 1; i < N + 1; i++) {
            if (indegree[i] == 0) {
                pq.add(i);
            }
        }
		
        while(!pq.isEmpty()) {
            int first = pq.poll();

            // 순서 출력
            System.out.print(first + " ");
			
            for (int next : list[first]) {
                indegree[next]--;
				
                if (indegree[next] == 0) {
                    pq.add(next);
                }
            }
        }
		
    }

}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%231766/src/Main.java