🔗 Problem

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

👩‍💻 Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 문제집

public class BJ1766 {

    static int n, m;
    static int[] numOfParents;
    static ArrayList<Integer>[] children;
    static PriorityQueue<Integer> queue = new PriorityQueue<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            children[a].add(b);
            numOfParents[b]++;
        }

        for(int i = 1; i <= n; i++) {
            if(numOfParents[i] == 0) {
                queue.add(i);
            }
        }

        solution();
        sb.append("\n");
        System.out.println(sb.toString());
    }

    private static void solution() {

        while(!queue.isEmpty()) {

            int poll = queue.poll();
            sb.append(poll + " ");
            deleteFromParents(poll);
        }
    }

    private static void deleteFromParents(int num) {

        for(int i = 0; i < children[num].size(); i++) {
            int x = children[num].get(i);
            numOfParents[x]--;
            if(numOfParents[x] == 0) queue.add(x);
        }
    }
    
}

📌 Note

아이디어

• 위상정렬 문제임을 캐치
• 각 문제 당 선행 문제 수를 numOfParents[]에 저장해둔다.
• numOfParents[x] == 0인 문제 x를 우선순위 큐에 넣고, 낮은 번호의 문제부터 뽑히도록 하였다.

시간초과 발생

• numOfParents[]를 사용할 생각을 못 하고 ArraysList<Integer>[] 타입의 부모를 담아두는 리스트를 생성하여, queue에서 뽑힌 문제마다 해당 리스트를 순회하도록 구현하였다.
• 그래서 시간초과 발생