위상정렬 java

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 그래프 정렬 알고리즘이다.

위상 정렬의 시간 복잡도는 **O(V + E)**로 문제를 해결할 수 있다.

위상 정렬은 DFS를 사용하여 구현하거나 indegree 배열을 사용하여 해결 가능하다.

indegree란?

한 정점에서 자신에게 들어오는 방향인 간선의 수를 의미한다.

위 그래프를 예로 들어보자.

• 1번 정점 : 2
• 2번 정점 : 0
• 3번 정점 : 1
• 4번 정점 : 1

위상 정렬 알고리즘

1. 간선의 정보를 받아 모든 정점의 indegree의 개수를 저장한다.
2. indegree가 0인 정점을 큐에 삽입한다.
3. 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다.
4. 제거 이후에 해당 indegree가 0이 된 정점을 큐에 삽입한다.
5. 큐가 빌 때까지 3, 4 과정을 반복한다.

위 과정에서 큐가 빈다면 사이클이 존재하므로 위상 정렬이 불가능하다.

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 의미다.
  • 위상 정렬은 사이클이 존재하면 안 된다!
  • 위 그래프를 Directed Acyclic Graph(DAG)라고 한다.
• 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과다.

이제 위상 정렬의 코드를 알아봅시다.

• 그래프의 관계를 표현하기 위한 2차원 Integer 배열
• 해당 노드의 indegree를 가지는 1차원 Integer 배열
• indegree 값이 0이 된 노드들을 담기위한 큐
• 위의 큐에서 꺼내져 결과로 출력하기 위해 담는 결과 큐

import java.util.*;

public class Main {
    static int N;

    public static void main(String[] args) {
        N = 7;
        int[] indegree = new int[N + 1];
        List<List<Integer>> array = new ArrayList<>();

        for (int i = 0; i <= N; i++)
            array.add(new ArrayList<>());

        // 간선 목록 input1 -> input2
        int[] input1 = {1, 1, 2, 4, 3, 3, 5, 2, 5};
        int[] input2 = {2, 3, 5, 6, 4, 7, 6, 4, 4};

        // 1. 간선의 정보를 받아 모든 정점의 indegree의 개수를 저장한다.
        for (int i = 0; i < input1.length; i++) {
            int node1 = input1[i];
            int node2 = input2[i];

            array.get(node1).add(node2);
            indegree[node2]++;
        }

        topologicalSort(indegree, array);
    }

    static void topologicalSort(int[] indegree, List<List<Integer>> array) {
        Queue<Integer> q = new LinkedList<>();
        Queue<Integer> result = new LinkedList<>();

        // 2. indegree가 0인 정점을 큐에 삽입한다.
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        /**
         * 3. 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다.
         * 4. 만약 indegree가 0 이 된다면 큐에 넣기
         * 5. 큐가 빌 때까지 3, 4 과정을 반복한다.
         */
        while (!q.isEmpty()) {
            int node = q.poll();
            result.offer(node);

            // 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다.
            for (Integer i : array.get(node)) {
                indegree[i]--;

                // 만약 indegree가 0 이 된다면 큐에 넣기
                if (indegree[i] == 0) {
                    q.offer(i);
                }
            }
        }

        System.out.println(result);
    }
}

위상 정렬 문제

• [ ] 줄 세우기
• [ ] ACM Craft
• [ ] 문제집
• [ ] 게임 개발
• [ ] 음악프로그램
• [ ] 작업
• [ ] 최종순위
• [ ] 임계경로