[백준] 1766번 - 문제집

 

1766번: 문제집

 

 

 

 

 

문제 

N개의 문제 중 a문제를 b문제보다 먼저 풀어야 하는 관계인 문제쌍 (a, b)가 M개 주어졌을 때, 문제를 풀어야 하는 순서를 출력하시오. 단, 가능한 쉬운 문제 먼저 풀어야 한다. 

 

 

 

 

 

조건 

1 <= N <= 32,000

1 <= M <= 100,000

시간 제한 2초

항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

 

 

 

 

풀이 방향

1번 ~ N번 문제를 정점, 문제간의 우선순위를 방향이 있는 간선이라고 생각하면 그래프로 치환하여 문제를 해결할 수 있다. 그런데 조건을 보면 '항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다' 라고 하였다. 문제를 모두 풀 수 없는 경우는 무엇일까? 아마도 문제를 풀 수 없는 경우는 풀어야 하는 순서가 A -> B -> C -> A 와 같이 사이클을 형성하여 어떤 문제를 우선 풀어야 하는지 알 수 없는 경우일 것이다. 따라서 해당 그래프는 순환하지 않는 방향 그래프라는 것을 짐작할 수 있다. 비순환 방향 그래프에서 우선순위를 결정할 수 있는 알고리즘인 위상정렬을 사용하면 문제가 풀릴 것이다. 

 

참고로 이 문제는 아래 문제를 먼저 해결하고 오면 보다 쉽게 풀이할 수 있다. 또한 아래 글에서 사용한 위상정렬 알고리즘과 이 문제에 사용한 방법이 크게 다르지 않으므로 이 글에서는 위상정렬 알고리즘을 구현하는 과정은 생략하도록 하겠다. 

[백준] 2252번 - 줄 세우기

 

다만, 이 문제의 경우 우선순위가 동등한 경우 더 쉬운 문제(문제 번호가 작은)를 먼저 풀어야 한다. 따라서 일반 큐를 사용하지 않고 완전 이진 형태의 힙 자료구조를 사용하는 우선순위 큐를 사용하여 큐에 담긴 문제가 오름차순 정렬되어 있도록 하면 된다. 큐에 담기는 조건은 차수(degree)가 0이 되는 문제(해당 문제보다 먼저 풀어야 하는 문제가 더이상 없는 경우)이므로, 큐에 담긴 문제들은 우선순위가 동등한 문제들이기 때문에 작은 번호의 문제를 먼저 꺼내어 출력 객체에 담아야 하기 때문이다. 

 

 

 

 

 

 

 

 

 

전체 코드

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

public class Main {
    public static void main (String[] args) throws IOException {
        new Main().solution();
    }
    
    
    private void solution () throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = {};
        
        input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        
        int[] degree = new int[N+1];
        List<Integer>[] link = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) link[i] = new ArrayList<>();
        
        
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            
            link[u].add(v);
            degree[v]++;
        }
        
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i = 1; i <= N; i++) {
            if (degree[i] == 0) pq.offer(i);
        }
        
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            
            int n = pq.poll();
            
            sb.append(n + " ");
            
            for (int num : link[n]) {
                if (--degree[num] == 0) {
                    pq.offer(num);
                }
            }
        }
        
        System.out.println(sb);
        
        br.close();
    }
}