오늘 풀어본 문제는
백준 1766번 문제집 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static PriorityQueue<Integer> pq;
    static ArrayList<ArrayList<Integer>> map;
    static int [] preCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        map = new ArrayList<>();
        preCnt = new int[n+1];

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

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

            map.get(fst).add(sec);
            preCnt[sec]++;
        }

        pq = new PriorityQueue<>();
        for(int i = 1; i <= n; ++i) if(preCnt[i] == 0) pq.add(i);

        StringBuilder sb = new StringBuilder();

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

            for(int i : map.get(cur))
            {
                preCnt[i]--;
                if(preCnt[i] == 0) pq.add(i);
            }
        }

        System.out.print(sb.toString());
    }
}

📝 풀이

map에 값을 입력받을 때, preCnt 배열에 선행될 문제의 갯수를 카운팅 해줍니다.
이를 활용하여 preCnt배열을 탐색하면서 선행될 문제가 없는 문제들만
우선순위큐에 담아준 상태로 시작합니다.
이렇게 되면 문제수가 작은 문제부터 풀어나가면서 preCnt 배열의 카운트 값을 줄여주고, 배열의 값이 0까지 줄었다는 의미는 선행될 문제가 더이상 없다는 의미이므로 해당 문제까지 큐에 담아줄 수 있습니다.

📜 후기

골드2길래 굉장히.. 쫄아서 시작했지만ㅠ 이전에 위상정렬 관련 문제를 풀어본 기억이 있어서 생각보다 금방 풀었습니다! 난이도가 괜히 사람을 참 떨리게하네요 ..ㅎㅎ