SWEA 1267: 작업순서

위상 정렬 O(V + E)

• 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해 주기 위한 알고리즘
• 위상 정렬은 사이클이 없는 그래프에서만 사용 가능하다.
• 스택 또는 큐를 이용해서 구현할 수 있다.

 

위상정렬의 구현 방법

1. 진입차수(부모 노드의 수)가 0인 정점을 큐에 넣는다
2. 큐에서 노드를 꺼내고, 이 노드에 연결된 모든 간선을 끊는다.
3. 간선 제거 이후 진입차수가 0이 된 정점을 넣는다.
4. 큐가 빌 때까지 2~3 반복

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

 

import java.util.*;
class Solution {
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int test = 10;
        for (int t = 1; t <= test; t++) {
            int v = in.nextInt(); // 정점
            int e = in.nextInt(); // 간선
 
            LinkedList<Integer> childs[] = new LinkedList[v + 1];
            for (int i = 0; i <= v; i++) {
                childs[i] = new LinkedList<Integer>();
            }
 
            int[] parentNum = new int[v + 1];
            boolean[] isVisited = new boolean[v + 1];
            for (int i = 0; i < e; i++) {
                int parentNode = in.nextInt();
                int childNode = in.nextInt();
 
                childs[parentNode].add(childNode);
                parentNum[childNode]++;
            }
 
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 1; i <= v; i++) {
                if (parentNum[i] == 0) {
                    queue.add(i);
                }
            }
 
            StringBuilder sb = new StringBuilder("#" + t + " ");
            while (!queue.isEmpty()) {
                int now = queue.poll();
                isVisited[now] = true;
                sb = sb.append(now + " ");
 
                LinkedList<Integer> links = childs[now];
                for (int node : links) {
                    parentNum[node]--;
                    if (!isVisited[node] && parentNum[node] == 0) {
                        queue.add(node);
                    }
                }
                links.clear();
            }
 
            System.out.println(sb);
        }
    }
}