알고리즘 기초 - 위상정렬

---

위상정렬이란?

---

방향 그래프(Directed Graph)에서 각 노드의 선행 조건을 고려하여 순서를 나열하는 것입니다.
즉, A가 B보다 먼저 수행되어야 한다면, A는 B보다 먼저 나온다 라는 규칙을 만족하는 순서를 찾는 거예요.

• 주로 작업 스케줄링, 과목 이수 순서, 프로젝트 작업 순서 등에 사용됩니다.
• 전제 조건: 그래프가 DAG(Directed Acyclic Graph, 사이클 없는 방향 그래프)**여야 합니다.
  • 사이클이 있으면 위상정렬이 불가능합니다.

 

---

위상정렬이 필요한 이유

---

예시 1: 과목 수강 순서

• “자료구조 → 알고리즘 → 프로젝트”
• 알고리즘을 듣기 전에 자료구조를 먼저 들어야 한다면, 위상정렬로 가능한 수강 순서를 결정할 수 있습니다.

예시 2: 프로젝트 작업 관리

• 프로젝트의 여러 작업 중 어떤 작업은 다른 작업이 끝나야 시작할 수 있습니다.
• 위상정렬을 통해 작업 순서를 자동으로 계산할 수 있습니다.

 

---

구현 방법

---

DFS(깊이 우선  탐색)

 

• 방문하지 않은 노드에서 DFS 시작
• DFS가 끝난 노드를 스택에 저장
• 모든 노드를 방문하면 스택을 뒤집어서 출력

def dfs(node):
    visited[node] = True
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(next_node)
    stack.append(node)

stack = []
visited = [False] * (n + 1)

for i in range(1, n+1):
    if not visited[i]:
        dfs(i)

stack.reverse()  # 위상정렬 순서
print(stack)

 

 

 

BFS(진입차수 이용)

 

• 각 노드의 진입 차수를 계산
• 진입 차수가 0인 노드를 큐에 넣기
• 큐에서 노드를 꺼내고 연결된 간선 제거 → 진입 차수가 0이 되면 큐에 넣기
• 큐가 빌 때까지 반복 → 위상정렬 완성

 

from collections import deque

queue = deque()
for i in range(1, n+1):
    if indegree[i] == 0:
        queue.append(i)

result = []
while queue:
    node = queue.popleft()
    result.append(node)
    for next_node in graph[node]:
        indegree[next_node] -= 1
        if indegree[next_node] == 0:
            queue.append(next_node)

print(result)

 

---

시간복잡도

---

 

• DFS/BFS 모두 O(V + E)
  • V: 노드 수
  • E: 간선 수
• 매우 효율적이면서 실무에서도 자주 사용됩니다.

 

---

마무리

---

 

위상정렬은 단순한 알고리즘이지만, 실무 프로젝트 관리, 빌드 시스템, 데이터 처리 순서 결정 등에서 반드시 알아두면 유용합니다.