BOJ 1766 : 문제집

문제링크

풀이요약

위상정렬, 우선순위 큐

풀이상세

1. 진입 차수에 따른 일의 순서를 정하는 위상정렬 문제. 단, 진입차수가 0인 문제들 가운데 가장 값이 적은 문제 순으로 풀어야 하므로 우선순위 큐를 활용한다.

2. 입력값을 통해 모든 값에 대한 진입차수를 체크한 후, 진입차수가 0인 값들을 시작으로 반복문을 실행한다.

3. 만약 문제를 먼저 풀어서 다음 문제에 대한 진입차수가 줄어드는 과정을 통해 진입차수가 0이 되는 경우 해당 값도 우선순위 큐에 반영하는 과정을 반복한다.

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

public class Main {
    static PriorityQueue<Integer>pq;
    static intN,M,d[];
    static List<Integer>v[];

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
N= Integer.parseInt(stk.nextToken());
M= Integer.parseInt(stk.nextToken());
v= new ArrayList[N+ 1];
d= new int[N+ 1];
        for (int i = 1; i <=N; i++) {
v[i] = new ArrayList<>();
        }
        for (int i = 0; i <M; i++) {
            stk = new StringTokenizer(br.readLine());
            int st = Integer.parseInt(stk.nextToken());
            int ed = Integer.parseInt(stk.nextToken());
v[st].add(ed);
d[ed]++;
        }
    }

    private static void solve() {
pq= new PriorityQueue<>();
        for (int i = 1; i <=N; i++) {
            if (d[i] == 0)pq.add(i);
        }

        StringBuffer sb = new StringBuffer();
        while (!pq.isEmpty()) {
            int curr =pq.poll();
            sb.append(curr).append(" ");
            for (int n :v[curr]) {
                if (--d[n] <= 0)pq.add(n);
            }
        }

        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception {
input();
solve();
    }
}