[PS] 백준 1766번 문제집

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

문제 설명

1번 부터 N번까지의 문제가 있다. 문제의 난이도는 1번이 제일 쉽고 그 다음이 2번, 3번, ..., N번이다. 다음 조건을 만족하는 문제 풀이 순서를 구하는 문제이다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

문제 풀이

p를 q보다 먼저 해야하고, r을 p보다 먼저해야하고... 와 같은 문제는 위상 정렬로 해결할 수 있다. 이 예시에서 p -> q -> r 의 선후관계가 존재하므로 DAG(Directed Acyclic Graph)로 문제들의 선후관계를 표현하고 위상 정렬을 수행하면 된다. 다만, 원래 위상 정렬에서는 여러 가능한 해가 존재할 수 있는데 이 문제에서는 그 순서를 가능하면 쉬운 문제부터 풀어야 한다는 제약을 주었으니 Priority Queue를 이용하여 풀어보았다.

위상 정렬은 정점 별 indegree 를 계산하고 시작해야 한다. 한 정점의 indegree는 Directed Graph 에서 그 정점으로 들어오는 간선의 수이다. 그 후, indegree == 0 인 정점을 모두 Priority Queue에 push한다. 그 이유는 indegree == 0 이라는 것은 그 정점을 방문하기 전에 먼저 방문할 정점이 없다는 것이기 때문이다. 즉, 아무런 제약 없이 방문할 수 있는 정점이라는 뜻이다. 그 정점의 인접 정점을 방문하면서 정점 번호를 출력한다. 방문 체크를 하고 방문한 정점의 indegree를 1만큼 감소시킨다. (현재 처리중인 정점 -> 인접 정점 이라는 의존관계가 해소 되었기 때문) 모든 인접 정점에 대해 수행한 후, Priority Queue에서 정점 하나를 꺼내 반복한다. 만약 그래프가 DAG가 아니었다면 방문한 정점의 개수가 그래프의 정점의 개수보다 적을 것이다.

요약
위상 정렬, Priority Queue로 풀이하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
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 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int n, m;
    static List<Integer>[] adj;
    static int[] inDegree;

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());

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

        adj = new ArrayList[n + 1];
        inDegree = new int[n + 1];

        for (int i = 1; i < n + 1; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            // DAG (Directed Acyclic Graph) 구성
            adj[from].add(to);
            inDegree[to]++;
        }

        topologySort();

        bw.flush();
    }

    static void topologySort() throws Exception {
        PriorityQueue<Integer> pq = new PriorityQueue();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                pq.add(i);
            }
        }

        while (!pq.isEmpty()) {
            int cur = pq.poll();

            bw.write(Integer.toString(cur) + " ");

            for (int adjNum : adj[cur]) {
                inDegree[adjNum]--;

                if (inDegree[adjNum] == 0) {
                    pq.add(adjNum);
                }
            }
        }
    }
}