문제

아이디어

위상정렬을 이용해서 풀 수 있는 문제이다.
기존 위상정렬 방법을 그대로 쓰면 쉬운 문제부터 풀지 않기 때문에 난이도별로 순회하면서 조건에 맞는 문제를 하나씩 추가해주면 된다.

풀 수 있는 조건의 문제는 다음과 같다.

이전에 풀지 않은 문제이면서, 선행 문제가 없는(혹은 이미 다 푼) 경우.
아래 코드에서는 visited == false && inDegree == 0인 경우에 해당한다.

한 문제를 푼 후에는, 인접 행렬을 통해 해당 문제가 선행 문제인 문제들을 찾아 선행문제를 풀었다고 처리해주면 된다.
아래 코드에서는 문제의 inDegree 값을 줄여주는 것으로 구현했다.

소스코드

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

public class Main {
    static int n;
    static int m;
    static StringTokenizer st;
    static BufferedWriter bw;
    static Prob[] problems;
    static ArrayList<Integer>[] adj;
    static int index = 0;


    static class Prob {
        int probNum;
        int inDegree;
        boolean visited;

        Prob(int probNum) {
            this.probNum = probNum;
            this.inDegree = 0;
            visited = false;
        }
    }

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        problems = new Prob[n + 1];
        adj = new ArrayList[n + 1];

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            adj[start].add(end);
            problems[end].inDegree += 1;
        }

        while (index++ < n) {
            int probNum = -1;
            for (int i = 1; i < n + 1; i++) {
                if (problems[i].inDegree == 0 && !problems[i].visited) {
                    probNum = i;
                    break;
                }
            }

            bw.write(probNum + " ");
            problems[probNum].visited = true;
            for (Integer i : adj[probNum]) {
                problems[i].inDegree--;
            }
        }

        bw.write("\n");
        bw.flush();
        bw.close();
    }
}

채점 결과

위상 정렬 구현 방식을 바꾸면서 더미 코드가 있었는데, 삭제한 후에 다시 제출해줬다.
원래는 시간 초과를 예상했지만, 통과한걸로 만족하기로 했다.
순회 방식을 바꿔준다면 실행 속도를 줄일 수 있을 것이다.