위상 정렬

위상 정렬이란?

: 정렬 알고리즘의 일종으로 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

ex) 선수과목을 고려한 학습 순서 결정

 

*진입 차수 : 특정한 노드로 들어오는 간선의 개수 

 

위상 정렬 알고리즘

1. 진입차수가 0인 노드를 큐에 넣는다

2. 큐가 빌 때까지 다음 과정을 반복한다

    - 큐에서 노드를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다

    - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

 

모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 가능하다.(보통 사이클이 발생하지 않는다고 문제에서 주어짐)

 

위 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력하면 위상 정렬의 결과값이다.

따라서 큐에 들어가는 원소의 순서에 따라 답이 여러가지 존재할 수 있다. 

 

시간 복잡도 : O(V+E)

 

 

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

public class TopologySort {
    static int v,e;
    static int[] indegree = new int[100001];   //진입차수
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    public static void topologySort() {
        ArrayList<Integer> result = new ArrayList<>(); //위상정렬 결과 담을 리스트
        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i <= v; i++) {
            if (indegree[i] == 0)
                q.offer(i);    //진입 차수가 0인 노드를 큐에 삽입
        }

        while (!q.isEmpty()) {
            int now = q.poll();
            result.add(now);
            for (int i = 0; i < graph.get(now).size(); i++) {
                //now 원소와 연결된 노드들의 진입차수에서 1 빼기
                indegree[graph.get(now).get(i)] -= 1;
                //새롭게 진입차수 0 되는 노드 삽입
                if (indegree[graph.get(now).get(i)] == 0)
                    q.offer(graph.get(now).get(i));
            }
        }

        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        v = sc.nextInt();
        e = sc.nextInt();

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

        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            indegree[b] += 1;
        }

        topologySort();
    }
}

 

 

참고

 

이것이 취업을 위한 코딩테스트다 with 파이썬