P.1766 문제집

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

    static int n, m;
    static int[] depth;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1];
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        depth = new int[n];
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            depth[line[1] - 1]++;
            graph[line[0] - 1].add(line[1] - 1);
        }

        for (Integer integer : topologicalSort()) bw.write(integer + " ");
        bw.flush();
    }

    private static ArrayList<Integer> topologicalSort() {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (depth[i] == 0) queue.add(i);
        }
        ArrayList<Integer> ans = new ArrayList<>();

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            ans.add(poll + 1);

            for (Integer integer : graph[poll]) {
                depth[integer]--;

                if (depth[integer] == 0) queue.add(integer);
            }
        }

        return ans;
    }
}

코드 설명

A문제를 풀기 위해서는 B문제를 풀어야한다.

즉, 특정 문제 간의 순서가 존재하므로 위상정렬을 이용했다.

//In main
depth = new int[n];
for (int i = 0; i < m; i++) {
    line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    depth[line[1] - 1]++;
}

//In topologicalSort()
for (int i = 0; i < n; i++) {
    if (depth[i] == 0) queue.add(i);
}
ArrayList<Integer> ans = new ArrayList<>();

while (!queue.isEmpty()) {
    Integer poll = queue.poll();
    ans.add(poll + 1);

    for (Integer integer : graph[poll]) {
        depth[integer]--;

        if (depth[integer] == 0) queue.add(integer);
    }
}

depth는 해당 문제의 선수 문제의 개수를 의미한다.

즉, 입력 예시 '3 1'과 같이 3번 문제를 풀고 1번 문제를 푸는 것이 좋다면 depth[1]이 증가한다.

 

문제 간의 순서가 존재하는 것은 위상정렬로 해결할 수 있는데

쉬운 문제(번호가 작은 순)를 먼저 풀어야 한다는 조건이 하나 더 있다.

이것은 priorityQueue를 이용해서 해결했다.

// In topologicalSort()
PriorityQueue<Integer> queue = new PriorityQueue<>();

만약 1번과 2번을 풀 차례가 되었다면 2번이 먼저 queue에 들어가더라도 1번 문제를 먼저 풀게 된다.