[백준 2252번] 줄 세우기 :: 늦깎이 IT

[백준 2252번] 줄 세우기 URL

이 문제는 위상정렬을 활용한 문제라기보다....위상정렬 그 자체이므로 이 포스팅에서 설명은 하지않겠습니다.

나중에 위상정렬에 대한 내용을 [알고리즘 이론] 카테고리에서 다루도록 하겠습니다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static List<Integer>[] list;
    static Stack<Integer> stack;
    static boolean[] visited, finished;
    static boolean isCycle = false;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        stack = new Stack<>();
        visited = new boolean[N + 1];
        finished = new boolean[N + 1];
        list = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++)
            list[i] = new ArrayList<Integer>();
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int st1 = Integer.parseInt(st.nextToken());
            int st2 = Integer.parseInt(st.nextToken());
            list[st1].add(st2);
        }
 
        for (int i = 1; i <= N; i++) {
            if (!finished[i])
                dfs(i);
        }
 
        if (!isCycle) {
            while (!stack.isEmpty())
                System.out.print(stack.pop() + " ");
        }
    }
 
    public static void dfs(int student) {
 
        visited[student] = true;
        for (int i = 0; i < list[student].size(); i++) {
 
            int adj = list[student].get(i);
 
            if (!visited[adj])
                dfs(adj);
            else if (!finished[adj])
                isCycle = true;
        }
        finished[student] = true;
        stack.push(student);
    }
}