위상 정렬(topological sort)

라면을 끓이는 상황을 떠올려보자. 냄비에 물을 붓고 불을 켠다. 그런데 물이 끓는 동안 가만히 기다려야 할까? 아니다. 그 사이에 봉지를 뜯고, 계란을 풀고, 그릇을 준비할 수 있다.

 

하지만 아무 순서로나 해도 되는 건 아니다. 물이 끓기 전에 면을 넣으면 제대로 익지 않고, 봉지를 뜯기도 전에 면을 꺼낼 수는 없다. 어떤 작업은 반드시 다른 작업이 끝난 뒤에야 시작할 수 있다는 것이다. 이런 의존 관계를 그래프로 나타내면 각 작업 간의 선후 관계가 명확해진다.

 

그렇다면 이 작업들을 어떤 순서로 해야 가장 빨리 라면을 끓일 수 있을까? 이번 글에서는 이런 문제를 해결하는 위상 정렬에 대해 알아보겠다.

 

1. 위상 정렬이란?

→

 

위상 정렬은 방향 그래프에서 각 정점들의 선후 관계를 지키면서 모든 정점을 일렬로 나열하는 알고리즘이다.

 

쉽게 말해, "A를 먼저 하고 B를 나중에 해야 한다"는 제약이 여러 개 주어졌을 때, 이 조건들을 모두 지키는 작업 순서를 찾는 것이다.

 

예를 들어 라면을 끓일 때 "물을 끓인 후 면을 넣어야 한다", "봉지를 뜯은 후 면을 꺼내야 한다" 같은 제약들이 있다면, 위상 정렬은 이 모든 조건을 만족하는 순서를 정해준다.

 

2. 위상 정렬의 조건

위상 정렬을 하려면 간선 (i, j)에 대해 정점 i가 반드시 정점 j보다 앞에 와야 한다. 즉, "A를 먼저 해야 B를 할 수 있다"는 화살표 방향을 모두 지키면서 정점들을 일렬로 세우는 것이다.

 

여기서 중요한 제약이 하나 있다. 그래프에 사이클이 있으면 안 된다는 것이다.

 

만약 A → B → C → A처럼 순환 구조가 있다면 어떻게 될까? A를 하려면 C가 끝나야 하고, C를 하려면 B가 끝나야 하고, B를 하려면 A가 끝나야 한다. 누구를 먼저 해야 할지 결정할 수 없다. 따라서 위상 정렬이 가능한 그래프는 방향 비순환 그래프(DAG, Directed Acyclic Graph)여야 한다.

 

3. 위상 정렬 구현 방법

위상 정렬을 구현하는 방법은 크게 두 가지가 있다. 하나는 진입 차수를 이용하는 방법이고, 다른 하나는 DFS를 이용하는 방법이다.

 

3.1. 진입 차수를 이용한 방법

 

이 방법의 핵심 아이디어는 "지금 당장 시작할 수 있는 작업을 먼저 한다"는 것이다

 

진입 차수란 어떤 정점으로 들어오는 간선의 개수를 말한다.

 

라면 끓이기로 비유하면, "물 끓이기"는 다른 작업에 의존하지 않으므로 진입 차수가 0이다. 반면 "라면 넣기"는 "물 끓이기"와 "봉지 뜯기" 두 작업이 끝나야 하므로 진입 차수가 2다.

 

알고리즘은 다음과 같이 동작한다.

1. 진입 차수가 0인 정점을 선택해 결과에 추가한다
2. 그 정점에서 나가는 간선들을 제거한다
3. 간선 제거로 진입 차수가 0이 된 정점이 생기면, 다시 1번부터 반복한다

 

이를 의사코드로 나타내면 다음과 같다.

 

다음은 위의 위상 정렬 방법을 시각화 한 그림이다.

 

3.2. DFS를 이용한 방법

위상 정렬은 DFS(깊이 우선 탐색)를 활용해서도 구현할 수 있다.

 

핵심 아이디어는 DFS 탐색이 끝나는 순서를 역순으로 기록하는 것이다.

 

정점을 방문할 때 그 정점에서 갈 수 있는 모든 곳을 먼저 탐색한 뒤, 탐색이 완전히 끝나면 그 정점을 스택에 추가한다. 모든 탐색이 끝난 후 스택을 뒤집으면 위상 정렬 결과가 된다.

 

왜 이 방법이 작동할까?

 

DFS는 한 정점에서 갈 수 있는 모든 후속 작업들을 먼저 처리한다. 따라서 어떤 정점의 탐색이 끝났다는 것은, 그 정점에 의존하는 모든 작업들이 이미 스택에 들어갔다는 의미다. 스택을 뒤집으면 자연스럽게 의존 관계가 지켜지는 순서가 된다.

 

의사코드는 다음과 같다. 

 

다음은 위의 위상 정렬 방법을 시각화 한 그림이다.

 

이렇게 두 가지 방법으로 위상 정렬을 구현할 수 있다.

 

진입 차수를 이용한 방법은 직관적이고 이해하기 쉬우며, DFS를 이용한 방법은 알고리즘이 간결하고 재귀의 우아함을 활용한다는 장점이 있다.

---

마지막으로 '위상 정렬'이라는 이름의 유래를 살펴보자.

 

 

이 용어는 수학의 위상수학에서 왔다. 위상수학은 물리적인 거리나 형태가 아닌 관계에 주목하는 학문이다. 예를 들어 커피잔과 도넛은 생김새가 전혀 다르지만, 위상수학에서는 같은 것으로 본다. 둘 다 구멍이 하나 있고, 찢거나 붙이지 않고 서로 변형할 수 있기 때문이다. 형태는 다르지만 본질적인 구조는 같다는 것이다.

 

위상 정렬도 같은 철학을 따른다. 그래프의 정점들이 물리적으로 어디에 위치하는지는 중요하지 않다. 중요한 건 오직 "누가 누구보다 먼저 와야 하는가"라는 순서 관계뿐이다. 물리적인 거리를 모두 지우고 순서 관계만 남겨서 정렬하는 것, 이것이 바로 위상 정렬이 '위상'이라는 이름을 갖게 된 이유다.

 

출처

쉽게 배우는 알고리즘 | 문병로 | 한빛아카데미 - 예스24