b1766. 문제집

 

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

 

 

 

이 문제는 위상 정렬을 사용해 방향 그래프의 노드를 순서대로 출력하는 문제다.
주어진 조건에 따라 노드를 정렬하고,
모든 진입 차수가 0인 노드부터 순차적으로 탐색해 결과를 출력하는 방식이다.

먼저 입력받은 노드 수와 간선 수를 통해 각 노드의 진입 차수를 기록하는 배열 degrees와

노드 간 연결 관계를 저장하는 lists 배열을 초기화한다.

이후 각 간선 정보를 입력받아 진입 차수를 증가시키고,
lists에 연결 정보를 저장한다.
이때 degrees[b]를 증가시켜 b로 들어오는 간선의 개수를 기록하고,
a에서 b로의 연결을 lists[a]에 추가한다.

초기화가 완료되면 진입 차수가 0인 노드를 모두 우선순위 큐 pq에 추가한다.
이 큐는 노드 번호가 작은 것부터 처리되도록 자동 정렬되며,
이를 통해 우선적으로 작은 번호의 노드가 선택된다.

이후 큐가 빌 때까지 위상 정렬을 수행하며,
큐에서 노드를 하나씩 꺼내 sb에 추가하고 해당 노드와 연결된 다음 노드들의 진입 차수를 감소시킨다.

만약 진입 차수가 0이 되면 다시 큐에 추가하여 다음 순서로 처리될 수 있도록 한다.
최종적으로 sb에 모든 정렬된 노드가 정답이 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int[] degrees;
    private static ArrayList<Integer>[] lists;
    private static PriorityQueue<Integer> pq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        degrees = new int[N+1];
        lists = new ArrayList[N+1];

        for (int i = 0; i <= N; i++) {
            lists[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= M ; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            degrees[b] += 1;
            lists[a].add(b);
        }

        pq = new PriorityQueue<>();

        for(int i = 1 ; i <= N ; i++){
            if(degrees[i] == 0){
                pq.add(i);
            }
        }

        // 위상 정렬
        while (!pq.isEmpty()){
            int now = pq.poll();
            sb.append(now).append(" ");
            for (int num : lists[now]){
                degrees[num] -= 1;
                if (degrees[num] == 0) {
                    pq.add(num);
                }
            }
        }

        System.out.println(sb);
    }
}