문제사항

골드 3단계 문제였다.

위상 정렬의 대표적인 문제로, 이론부터 알아보자.

위상 정렬이란?

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

위상정렬은 항상 유일한 값으로 정렬되지 않는다. (순서 보장 X)

진입 차수 : 자기 자신을 가리키는 에지의 개수

왼쪽 그래프를 ArrayList로 표현하면 우측 블럭과 같은 형태로 나타난다.

이때 진입차수 값을 계산하면 1은 2와 3을 가리키고 있기 때문에 2의 진입차수는 1, 3의 진입차수는 1을 가지게 된다.

마찬가지로 2가 4,5를 가리키고 있기에 4의 진입차수는 1, 5의 진입차수는 1을 가지게 된다.

1~5까지 각 노드가 가리키는 노드에 대한 진입차수를 계산하여 진입차수 배열로 초기화 시키면 위와 같이 나타난다.

초기화 시킨 진입차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.

그 후 인접 리스트에서 선택된 노드가 가르키는 노드들의 진입 차수를 1씩 뺀다

모든 노드가 정렬될 때까지 반복해준다.

앞서 말했듯이 진입 차수가 0인 노드가 여러 개일 때 어느 것을 먼저 넣어도 위배되지 않는다는 것을 기억하자.

위상 정렬 배열 결과는 위와 같이 나타난다.

알고리즘 분류

1. 그래프 (위상 정렬)

코드

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

public class Main {
    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());
        //진입차수 저장 배열
        int[] arr = new int[n + 1];
        //그래프 2차원 리스트
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(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());
            list.get(a).add(b); //a가 b 앞에 선다. = a가 b를 가리킨다.  2차원 리스트 정보 초기화
            arr[b]++; //b의 진입차수 +1
        }

        Queue<Integer> que = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (arr[i] == 0) { //i의 진입차수 값이 0이라면
                que.offer(i); //큐에 저장
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!que.isEmpty()) {
                int num = que.poll(); // 큐에서 꺼냄 (동시에 삭제)
                sb.append(num).append(" "); //반환값에 추가

                for (int j = 0; j < list.get(num).size(); j++) {
                    int edge  = list.get(num).get(j); // 만약 num이 4이고, 4가 가리키는 숫자가 2였다면 edge는 2를 반환
                    arr[edge]--; // edge의 진입차수 -1
                    if (arr[edge] == 0) { // edge가 0이 되면 큐에 저장
                        que.offer(edge);
                    }
                }
            }
        }

        System.out.println(sb);
    }
}