[알고리즘] 백준 2252 줄 세우기 - JAVA

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

위상정렬을 통한 문제 풀이라기 보다는 위상정렬 그 자체를 구현하는 문제라고 생각한다.

 

따로 설명은 필요 없을것 같다.

 

이해가 가지 않는다면 나동빈님 블로그(m.blog.naver.com/ndb796/221236874984)를 참고해서 공부해보자. 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    static int n;
    static int m;
    static int[] degree;
    static List<Integer>[] list;

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        degree = new int[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++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            list[x].add(y);
            degree[y]++;
        }
        // input end
        topologySort();
    }

    static void topologySort() {
        Queue<Integer> queue = new LinkedList<Integer>();

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

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");

            for (int i = 0; i < list[current].size(); i++) {

                int next = list[current].get(i);
                degree[next]--;

                if (degree[next] == 0) {
                    queue.add(next);
                }
            }

        }
    }

}