BOJ02252 줄 세우기

https://www.acmicpc.net/problem/2252 (opens new window)

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세운다.

위상 정렬

위상 정렬 (opens new window)

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

while (!queue.isEmpty()) { // (2)
    Integer node = queue.poll();
    result.add(node);

    for (Integer target : graph.get(node)) { // (3)
        indegree[target]--;

        if (indegree[target] == 0) { // (4)
            queue.add(target);
        }
    }
}

(1) 진입 차수가 0인 노드를 모두 queue에 저장한다.
(2) queue가 빌 때 까지 반복하기 위한 반복문이다.
(3) 해당 노드가 가리키는 진입 차수를 -1 차감한다.
(4) 만약 해당 노드가 0인 경우 queue에 추가한다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BOJ2252 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[n + 1];

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

        for (int i = 0; i < m; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();

            graph.get(start).add(end);
            indegree[end]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

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

        while (!queue.isEmpty()) {
            Integer node = queue.poll();
            result.add(node);

            for (Integer target : graph.get(node)) {
                indegree[target]--;

                if (indegree[target] == 0) {
                    queue.add(target);
                }
            }
        }

        for (Integer i : result) {
            System.out.print(i + " ");
        }
    }
}

#BOJ #그래프 이론 #위상 정렬