[크래프톤 정글] 위상정렬 개념 정리

Algorithm

[크래프톤 정글] 위상정렬 개념 정리

하루이2222 2024. 9. 26. 02:26

위상 정렬(Topological Sorting)의 개념

위상 정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선후 관계에 따라 순서대로 나열하는 것이다. 여기서 선후 관계란 그래프의 방향을 나타내는 간선(Edge)에 의해 결정되는 노드 간의 의존성을 의미한다. 위상 정렬의 목적은 이 의존성을 지키면서 모든 노드를 나열하는 것이다.

위상 정렬의 기본 개념

방향 그래프(Directed Graph):
- 그래프의 각 간선이 방향을 가지며, 이는 한 노드에서 다른 노드로의 일방향성 연결을 의미한다.
- 예를 들어, 작업 A가 끝나야 작업 B를 시작할 수 있다면, 이는 A에서 B로 향하는 방향 간선으로 표현된다.
사이클이 없는 그래프(Acyclic Graph):
- 그래프에 사이클(Cycle)이 없다는 것은, 그래프를 따라 한 노드에서 출발해 다시 그 노드로 돌아오는 경로가 존재하지 않는다는 의미다.
- 사이클이 있는 경우, 위상 정렬은 불가능하다. 예를 들어, A → B → C → A의 사이클이 있다면, A, B, C 중 어느 것도 먼저 처리될 수 없기 때문이다.
위상 정렬의 정의:
- 위상 정렬은 DAG에서 노드들을 나열하는 방식으로, 각 노드 (u)가 다른 노드 (v)로 가는 간선을 가진다면, 위상 정렬 결과에서 (u)는 항상 (v)보다 앞에 위치해야 한다.
- 예를 들어, (u \rightarrow v)라는 간선이 있다면, 위상 정렬에서 (u)는 반드시 (v)보다 먼저 나와야 한다.

위상 정렬의 예시

위상 정렬을 설명하기 위해 간단한 그래프를 예로 들어보자:

   A → C → E
   ↓   ↓
   B → D → F

이 그래프에서 A, B, C, D, E, F는 노드이고, 간선은 작업 간의 선후 관계를 나타낸다.
위상 정렬의 가능한 결과 중 하나는 A, B, C, D, E, F로, 이는 작업을 수행해야 하는 순서를 나타낸다.
- A와 B는 다른 작업에 선행해야 하므로 제일 먼저 나온다.
- C는 A와 B가 끝난 후에, D는 C와 B가 끝난 후에 나와야 한다.
- E는 C가 끝난 후, F는 D와 E가 끝난 후에 나와야 한다.

위상 정렬이 왜 중요한가?

위상 정렬은 다양한 분야에서 의존 관계가 있는 작업들을 처리하는 순서를 결정하는 데 매우 유용하다. 몇 가지 중요한 이유는 다음과 같다:

작업 스케줄링:
- 위상 정렬을 사용하면 작업 간의 의존 관계를 고려하여, 어떤 순서로 작업을 수행해야 하는지 결정할 수 있다. 예를 들어, 소프트웨어 컴파일러가 파일 간의 의존성 순서를 정하는 데 사용된다.
선수 과목 이수:
- 학습 커리큘럼에서, 특정 과목을 수강하기 전에 반드시 이수해야 하는 선수 과목들이 있을 때, 위상 정렬을 통해 전체 이수 순서를 결정할 수 있다.
프로젝트 관리:
- 대규모 프로젝트에서, 특정 작업들이 다른 작업들에 의존할 때, 위상 정렬을 통해 프로젝트 진행 순서를 효율적으로 정리할 수 있다.

위상 정렬의 특징

순서가 유일하지 않다:
- 위상 정렬은 항상 유일한 결과를 가지지는 않는다. 즉, 위상 정렬의 결과는 여러 가지가 될 수 있다. 위의 예시 그래프에서 A, B, C, D, E, F 외에도 다른 여러 가능한 순서들이 있다.
사이클이 없는 그래프에서만 가능:
- 위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다. 만약 그래프에 사이클이 있다면, 그 그래프는 위상 정렬을 할 수 없다.
순서 보장:
- 위상 정렬은 그래프 내에서 간선에 의해 정의된 모든 의존 관계를 보장한다. 즉, 선행 작업이 먼저 수행되고 후행 작업이 나중에 수행되도록 정렬된다.

위상 정렬을 찾는 방법

위상 정렬을 찾는 대표적인 방법은 두 가지가 있다:

Kahn’s Algorithm (큐 기반 방법):
- 진입 차수(In-degree)를 이용하여 노드의 순서를 결정한다. 먼저 진입 차수가 0인 노드들을 큐에 넣고, 큐에서 노드를 하나씩 꺼내며 그 노드와 연결된 간선을 제거한다. 이 과정을 반복하면서 순서를 정한다.
DFS 기반 방법:
- DFS(깊이 우선 탐색)를 사용하여 노드들을 탐색한 뒤, 모든 인접 노드들을 처리한 후 스택에 노드를 추가한다. DFS가 끝난 후 스택에서 노드를 꺼내면 위상 정렬이 된다.

위상 정렬의 예시 코드 (Kahn's Algorithm)

from collections import deque

def kahn_topological_sort(graph):
    # 진입 차수 초기화
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # 진입 차수가 0인 노드를 큐에 추가
    queue = deque([node for node in graph if in_degree[node] == 0])

    topo_order = []

    while queue:
        node = queue.popleft()
        topo_order.append(node)

        # 해당 노드의 이웃 노드들의 진입 차수를 감소
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 그래프가 DAG가 아닌 경우
    if len(topo_order) != len(graph):
        raise ValueError("Graph has a cycle, topological sorting not possible.")

    return topo_order

# 예시 그래프
graph = {
    'A': ['C', 'D'],
    'B': ['D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

# 위상 정렬 실행
print(kahn_topological_sort(graph))  # ['A', 'B', 'C', 'D', 'E', 'F']

위상 정렬의 한계와 주의점

사이클 감지:
- 위상 정렬 과정에서 큐가 비었는데도 모든 노드를 처리하지 못했다면, 그래프에 사이클이 있는 것이다. 이는 위상 정렬이 불가능하다는 것을 의미한다.
순서의 비유일성:
- 여러 개의 위상 정렬 결과가 나올 수 있다. 예를 들어, 어떤 노드들이 서로 독립적이라면, 그 순서는 여러 가지로 조합될 수 있다.

위상 정렬의 시간 복잡도

시간 복잡도: (O(V + E))
- (V)는 노드의 수, (E)는 간선의 수를 의미한다.
- 그래프의 모든 노드와 간선을 한 번씩 방문하기 때문에 시간 복잡도는 (O(V + E))이다.

결론

위상 정렬은 그래프 이론에서 매우 중요한 개념으로, 사이클이 없는 방향 그래프에서 각 노드 간의 의존성을 유지하면서 순서를 정하는 알고리즘이다. 작업 스케줄링, 교육 과정 설계, 프로젝트 관리 등 여러 실생활 문제를 해결하는 데 사용된다. 위상 정렬은 사이클이 없는 그래프에서만 가능하며, 여러 가지 가능한 순서가 존재할 수 있다. Kahn's Algorithm과 DFS 기반 방법이 가장 널리 사용되는 구현 방법이다.