[백준] 1766 문제집 - Graph Theory / Java

• 문제 링크

1766번: 문제집

 

• 풀이 과정

[백준] 2252 줄 세우기 - Graph Theory / Java

위의 문제와 같은 구조로 어떤 문제를 풀기 위하여 선행되어야 하는 문제의 개수,

즉 진입 차수를 inDegree 배열에 저장하여 위상 정렬로 풀이한다.

 

다만 쉬운 문제부터 먼저 풀어야 하는 조건에 의해 작은 수부터 먼저 반환하는 우선 순위 큐를 활용한다.

 

문제 i 에 대하여 먼저 풀어야하는 문제가 없을 경우(inDegree[i] == 0) 우선 순위 큐에 삽입하고,

우선 순위 큐의 기본 성질에 따라 문제의 난이도가 낮은 순서로 풀이한다.

해당 문제가 풀이됨에 따라 특정 문제의 진입 차수의 값을 감소시켜 해당 값이 0 일 경우 우선 순위 큐에 삽입한다.

 

이렇게 위상 정렬의 조건을 만족하여 우선 순위 큐에 삽입된 값들을 크기가 작은 순서로 반환 및 정답으로써 출력된다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<List<Integer>> list = new ArrayList<>();
        int[] inDegree = new int[n + 1];

        for (int i = 0; i <= n; i++)
            list.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            list.get(u).add(v);
            inDegree[v]++;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0)
                pq.offer(i);
        }

        while (!pq.isEmpty()) {
            int node = pq.poll();
            bw.write(node + " ");

            for (int v : list.get(node)) {
                inDegree[v]--;

                if (inDegree[v] == 0)
                    pq.offer(v);
            }
        }

        bw.flush();
    }

}