[백준] 2252번 - 줄 세우기 (Gold 3)

문제 링크

백준 2252번 - 줄 세우기 (Gold 3)

문제 설명

N명의 학생들을 키 순서대로 줄을 세우려고 한다.
일부 학생들의 키를 비교한 결과만이 주어져있을 때, 가능한 줄 세우기 결과를 출력하시오.
여러가지가 가능하다면 아무거나 한 가지만 출력한다.

정답 코드 및 설명

전형적인 위상정렬 문제이다.
이 문제에서는 DFS를 활용하여 위상정렬을 수행하였다.
A가 B 앞에 서야한다면 A를 B의 부모로 두는 그래프를 만들자.
이 그래프에서 DFS를 수행하고, 탐색이 끝난 정점을 스택에 집어넣는 과정을 반복한다.
모든 정점이 탐색되었을 때 스택에서 순서대로 꺼내면 위상정렬이 완료된다.

이 과정이 성립하는 이유는 DFS에서 탐색이 완료되는 순서는 깊은, 즉 뒤에 다른 정점이 오지 않는 순이기 때문이다.
말로는 사실 이해가 쉽지 않은데, 예를 들면 이해가 편하다.
주어진 관계가 2 1, 1 3, 1 4, 2 4라고 하면 알고리즘은 아래와 같은 순서로 실행된다.

1. 1번 정점에서 시작하는 DFS : 1번 정점의 자식인 3, 4번 정점을 탐색한다.
2. 3번 정점에서 시작하는 DFS : 자식이 없다. 탐색이 완료된 3번 정점을 스택에 넣는다.
3. 4번 정점에서 시작하는 DFS : 자식이 없다. 탐색이 완료된 4번 정점을 스택에 넣는다.
4. 1번 정점으로 돌아옴 : 탐색하지 않은 자식이 없다. 탐색이 완료된 1번 정점을 스택에 넣는다.
5. 2번 정점에서 시작하는 DFS : 탐색하지 않은 자식이 없다. 탐색이 완료된 2번 정점을 스택에 넣는다.
6. 스택에서 순서대로 꺼내서 출력 : 2 1 4 3

처음에 루트가 아닌 다른 노드에서 출발할 경우도 깔끔하게 처리되는 것을 볼 수 있다.

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

public class BOJ2252 {
    int n;
    ArrayList<Integer>[] order;
    boolean[] isChecked;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        order = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            order[i] = new ArrayList<>();
        }
        int m = Integer.parseInt(st.nextToken());
        int front, back;
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            front = Integer.parseInt(st.nextToken()) - 1;
            back = Integer.parseInt(st.nextToken()) - 1;
            order[front].add(back);
        }
    }

    void topologicalSort() {
        isChecked = new boolean[n];
        Stack<Integer> sorted = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (isChecked[i]) continue;
            dfs(i, sorted);
        }
        print(sorted);
    }

    void dfs(int i, Stack<Integer> sorted) {
        if (isChecked[i]) return;
        isChecked[i] = true;
        for (int next : order[i]) {
            dfs(next, sorted);
        }
        sorted.push(i + 1);
    }

    void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(' ');
        }
        System.out.println(sb);
    }

    void solution() throws IOException {
        input();
        topologicalSort();
    }

    public static void main(String[] args) throws IOException {
        new BOJ2252().solution();
    }
}