[BOJ] 2252. 줄 세우기 (🥇, 위상 정렬)

🔗

풀이

A B 가 주어지면 A가 B의 앞에 선다는 뜻이 된다. 어떤 순서로 줄을 서게 되는지 구하는 문제로 답은 여러 가지가 존재할 수 있다.

처음에는 dp나 누적합 정도로 풀 수 있겠다 생각하고 A 가 앞에 있으니 -1을 하고 B 가 뒤에 있으니 +1을 하는 방식으로 어느 정도 앞에 있는지, 어느 정도 뒤에 있는지 여부를 가지고 판단하려고 했지만 테스트케이스처럼 간단한 경우는 통과하는데 복잡한 그래프 형태를 띈 경우는 불가능했다.

그래서 찾아보니 위상 정렬 알고리즘을 사용해야 했다.

위상 정렬은 위와 같이 방향이 있는 비순환 그래프의 경우에만 가능하다. 순환을 하게 되면 순서를 정할 수 없고, 방향이 없어도 순서를 정할 수 없기 때문이다.

위상 정렬을 하기 위해서는 2가지가 필요하다. 진입차수와 해당 정점과 연결된 다음 정점에 대한 정보이다. 진입차수는 해당 정점으로 들어오는 정점의 개수이고, 연결된 다음 정점에 대한 정보들은 리스트 형태로 저장하게 된다.

진입차수가 0인 정점부터 시작을 하게 된다. 시작 정점의 개수는 여러 개일 수 있다. 진입차수가 0인 모든 정점에 대해 큐에 저장하고 하나씩 꺼내서 연결된 다른 정점들에 대해 진입차수를 1씩 깎아준다. 이렇게 해나가면서 또 새롭게 진입차수가 0이 되는 정점들에 대해 큐에 저장하는 방식을 반복한다. 큐에서 꺼내는 순서가 위상 정렬을 진행한 순서가 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] inDegree = new int[N]; // 진입 차수
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }

        int A;
        int B;
        for (int i = 0; i < M; i++) {
            A = sc.nextInt();
            B = sc.nextInt();
            inDegree[B-1]++;
            graph.get(A-1).add(B-1);
        }

        Queue<Integer> queue = findStart(inDegree);

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node+1)
              .append(" ");

            List<Integer> linkedNode = graph.get(node);
            for (Integer i : linkedNode) {
                inDegree[i]--;
                if (inDegree[i] == 0) {
                    queue.add(i);
                }
            }
        }

        System.out.println(sb);
    }

    private static Queue<Integer> findStart(int[] inDegree) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        return queue;
    }
}