[BOJ] 문제집

[1766] 문제집

www.acmicpc.net/problem/1766

 

 

Solution

• N개의 문제를 모두 풀어야하는데, 문제 풀이 순서에 있어 두 가지 조건을 고려해야한다.
• 첫째, 숫자가 작은 문제부터 풀어야한다.
• 둘째, 먼저 풀어야하는 길잡이 문제부터 풀어야 한다.
• 일반적인 위상정렬에서 q를 오름차순 pq로 바꾸어 쉽게 풀 수 있었다.
• 알고리즘 분류가 우선순위 큐로 되어있길래 풀었는데, 위상정렬 문제였다. 덕분에 위상정렬 공부까지 했음.

4ngeunlee.tistory.com/365

[Algorithm] 위상 정렬

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n, m;
    static int[] indegree;
    static List<List<Integer>> graph;
    static StringBuilder sb;
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
 
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        indegree = new int[n + 1];
 
        int a, b;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = stoi(st.nextToken());
            b = stoi(st.nextToken());
 
            graph.get(a).add(b);
            indegree[b]++;
        }
 
        topologicalSort();
 
        System.out.println(sb.toString().trim());
    }
 
    private static void topologicalSort() {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        for (int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0){
                pq.offer(i);
            }
        }
 
        sb = new StringBuilder();
        while (!pq.isEmpty()) {
            int p = pq.poll();
            sb.append(p + " ");
 
            for (int node : graph.get(p)) {
                indegree[node]--;
 
                if (indegree[node] == 0) {
                    pq.offer(node);
                }
            }
        }
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
 
}