anonymous.rs

알고리즘: 위상 정렬 (Topological Sort)

9 min read

위상 정렬 (Topological Sort) 완벽 가이드

소프트웨어 엔지니어링 인터뷰에서 작업의 순서, 빌드 시스템, 또는 선수과목(Prerequisite)과 관련된 문제가 나온다면 가장 먼저 떠올려야 하는 알고리즘, 바로 **위상 정렬(Topological Sort)**입니다.

1. 위상 정렬이란?

위상 정렬은 **방향 그래프(Directed Graph)**에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘입니다.

쉽게 말해, **“순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘”**입니다.

필수 조건: DAG (Directed Acyclic Graph)

위상 정렬이 성립하기 위해서는 그래프가 반드시 **사이클이 없는 방향 그래프(DAG)**여야 합니다. 만약 그래프 내에 사이클(순환)이 존재한다면, 어떤 작업이 먼저 수행되어야 하는지 모순이 발생하므로 위상 정렬을 수행할 수 없습니다.

2. 핵심 개념: 진입차수 (In-degree)

위상 정렬 알고리즘을 이해하기 위해 가장 중요한 개념은 **진입차수(In-degree)**입니다.

  • 진입차수 (In-degree): 특정 정점으로 들어오는 간선의 개수. 즉, 해당 작업을 수행하기 위해 먼저 완료되어야 하는 ‘선수 작업’의 개수를 의미합니다.
  • 진출차수 (Out-degree): 특정 정점에서 나가는 간선의 개수.

진입차수가 0이라는 것은 선수 작업이 없다는 뜻이므로, 당장 시작할 수 있는 작업임을 의미합니다.

3. 위상 정렬 알고리즘 동작 과정 (Kahn’s Algorithm - 큐 사용)

가장 직관적이고 널리 사용되는 큐(Queue)를 이용한 위상 정렬 알고리즘의 동작 순서는 다음과 같습니다.

  1. 그래프의 각 정점의 진입차수를 계산하여 배열에 저장합니다.
  2. 진입차수가 0인 모든 정점을 큐(Queue)에 삽입합니다. (시작 가능한 작업들)
  3. 큐가 빌 때까지 다음 과정을 반복합니다:
    • 큐에서 원소(정점)를 하나 꺼냅니다. (이 순서가 위상 정렬의 결과가 됩니다)
    • 꺼낸 정점과 연결된 모든 간선을 그래프에서 제거합니다. (즉, 연결된 도착 정점들의 진입차수를 1씩 감소시킵니다)
    • 진입차수가 새롭게 0이 된 정점을 큐에 삽입합니다.
  4. 결과 확인: 큐에서 꺼낸 정점의 개수가 전체 정점의 개수와 같다면 위상 정렬이 성공적으로 완료된 것입니다. 만약 꺼낸 정점의 개수가 더 적다면, 그래프에 사이클이 존재하여 위상 정렬을 완성할 수 없었음을 의미합니다.

참고: 스택(Stack)을 활용한 DFS(깊이 우선 탐색) 방식으로도 위상 정렬을 구현할 수 있습니다.

4. 파이썬(Python) 구현 예시

큐(Queue)를 활용하여 대학의 선수과목 순서를 구하는 간단한 위상 정렬 코드를 구현해 보겠습니다.

from collections import deque
 
def topological_sort(v, edges):
    # v: 정점의 개수, edges: 간선 정보 리스트 (출발, 도착)
    
    # 인접 리스트 초기화 및 진입차수 테이블 초기화 (모든 정점 0)
    graph = [[] for _ in range(v + 1)]
    in_degree = [0] * (v + 1)
    
    # 방향 그래프 간선 정보 및 진입차수 세팅
    for start, end in edges:
        graph[start].append(end)
        in_degree[end] += 1  # 도착 정점의 진입차수 1 증가
        
    result = [] # 알고리즘 수행 결과를 담을 리스트
    queue = deque()
    
    # 1. 진입차수가 0인 정점을 큐에 삽입
    for i in range(1, v + 1):
        if in_degree[i] == 0:
            queue.append(i)
            
    # 2. 큐가 빌 때까지 반복
    while queue:
        current = queue.popleft()
        result.append(current)
        
        # 해당 정점과 연결된 노드들의 진입차수에서 1 빼기
        for next_node in graph[current]:
            in_degree[next_node] -= 1
            
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if in_degree[next_node] == 0:
                queue.append(next_node)
                
    # 3. 사이클 판별
    # 결과 리스트의 길이가 정점의 개수와 다르다면 사이클이 존재한다는 뜻
    if len(result) != v:
        return "Cycle detected! 위상 정렬 불가"
        
    return result
 
# 실행 예시 (정점 6개)
# 1->4, 1->5, 2->3, 2->4, 3->6, 4->6, 5->6
v = 6
edges = [(1, 4), (1, 5), (2, 3), (2, 4), (3, 6), (4, 6), (5, 6)]
 
print("위상 정렬 결과:", topological_sort(v, edges))
# 출력 가능한 결과 중 하나: [1, 2, 5, 4, 3, 6] 
# (진입차수가 0인 노드가 여러 개일 경우, 큐에 들어가는 순서에 따라 여러 정답이 존재할 수 있습니다)

5. 시간 복잡도

위상 정렬의 시간 복잡도는 입니다. (V는 정점의 개수, E는 간선의 개수)

  • 초기화 단계에서 모든 정점의 진입차수를 갱신하기 위해 간선을 모두 확인합니다:
  • 큐에 정점을 넣고 빼면서 각 정점은 정확히 한 번씩만 처리되며, 각 정점에서 나가는 간선들을 확인합니다:
  • 따라서 전체 시간 복잡도는 로, 매우 빠르게 순서를 결정할 수 있습니다.

6. 활용 사례

면접에서 다음과 같은 키워드가 나온다면 위상 정렬을 적용해야 하는 문제입니다.

  1. 빌드 시스템 (Build Systems): 소스 코드 파일 간의 의존성을 파악하여 컴파일 순서를 결정할 때 (예: Make, Makefile).
  2. 선수과목 (Prerequisite Courses): 특정 과목을 듣기 위해 먼저 수강해야 하는 과목이 정해져 있는 대학 커리큘럼 계획.
  3. 작업 스케줄링 (Task Scheduling): 일련의 작업들 사이에 선후 관계가 명확히 주어졌을 때의 작업 순서 배정.
  4. 패키지 관리자 (Package Managers): npm, pip 등에서 패키지를 설치할 때, 의존성이 있는 다른 패키지들을 먼저 설치하는 순서를 계산할 때.

요약

위상 정렬(Topological Sort)은 선후 관계가 명확하게 정의된 작업들을 올바른 순서로 나열해야 할 때 사용하는 그래프 알고리즘입니다. **DAG(Directed Acyclic Graph)**에서만 동작하며, **진입차수(In-degree)**와 **큐(Queue)**를 활용하여 의 시간 복잡도로 해결할 수 있다는 점, 그리고 사이클 판별까지 가능하다는 점을 인터뷰에서 확실하게 설명할 수 있어야 합니다.

Graph View