[알고리즘] 위상 정렬(Topological Sort) [ 백준 2252번 - 줄 세우기 ]

2024년 11월 26일

위상 정렬

 

위상 정렬이란, 순환하지 않는 유향 그래프(DAG, Directed Acyclic Graph)를 방향성에 거스르지 않도록 순서대로 배열하는 방법이다.

 

이게 무슨 의미인가. 다음 예시를 통해 쉽게 이해해보자.

 

나는 어떤 RPG 게임을 시작하려고 한다.

해당 RPG 게임에서는 첫 레이드인 A 보스 레이드에 참여하기 위해서 50레벨을 달성하고 모든 장비 강화를 10단계 이상 달성해야 한다.

그리고 다음 레이드인 B 보스 레이드에 참여하기 위해서, A 보스 레이드를 클리어한 상태에서 모든 장비 강화를 15단계 이상 달성해야 한다.

그리고 장비를 업그레이드 하기 위해서는 B 보스 레이드를 클리어한 상태에서 기존 장비를 상위 장비로 계승해야 한다.

 

어떤 RPG 게임에서 내가 이룩하고 싶은 최종 목표가 상위 장비로 업그레이드 하는 것이라면, 아래 그림과 같이 나타낼 수 있을 것이다.

 

 

50레벨을 달성했지만 모든 장비를 10강까지 맞추지 못했다면 A 보스 레이드에 입장할 수 있는 자격을 얻지 못할 것이고, 모든 장비를 10강까지 맞췄지만 50레벨을 달성하지 못했다면 똑같이 자격을 얻지 못할 것이다.

 

결국 둘 다 달성해야 A 보스 레이드에 입장할 수 있고, 이후 선수 과정을 마쳐야 다음 단계를 진행하며 최종적으로 장비 계승이라는 목표에 도달할 수 있을 것이다.

 

위상 정렬은 쉽게 말해, 순서가 정해져 있는 일련의 작업을 차례대로 수행하는 방법을 구하는 알고리즘이다.

 

내가 장비 계승까지 도달하는 방법은 아래와 같이 여러 가지이다.

 

 

 

이 외에도 여러 가지 방법이 있을 수 있다.

 

여기에서 알 수 있듯이, 위상 정렬 알고리즘을 통해 구한 해답은 여러 가지가 될 수 있다는 특징을 가지고 있다.

 

왜 순환하지 않는 방향 그래프(DAG)여야 하는가?

 

무향 그래프라면 정렬의 의미가 없으며, 유향 그래프라도 순환하는 그래프라면 위상 정렬이 불가능하다.

 

 

초록색 간선으로 장비계승 -> 캐릭터 생성을 이어주었을 때, 사이클이 생기게 된다.

그림을 보면 느낄 수 있듯, 장비를 계승한 다음 이미 다 키운 캐릭터를 또 생성하는 모순적인 상황이 연출된다.

(여기서 캐릭터 생성은 다른 캐릭터를 생성한다는 의미가 아닌 이미 만든 캐릭터를 중복해서 만든다는 의미로 해석해야 한다.)

 

따라서 순환하지 않는 방향 그래프가 아니라면

1. 시작점을 특정할 수 없으며,
2. 먼저 진행해야 하는 과정을 나중에 진행해도 되는 모순이 발생하게 된다.
3. 그렇기 때문에 정렬의 의미가 무색해지게 된다.

그러므로 위상 정렬이 불가능하게 된다.

 

 

흐름도 및 구현

 

위상 정렬은 진입 차수(in_degree)를 활용한 BFS 방식과 DFS방식으로 구현이 가능하다.

이번 포스팅에선 진입 차수를 활용한 BFS 방식을 설명할 것이다.

또한 해당 방식은 세부적으로 Queue 자료구조와 Stack 자료구조를 활용하는 방식에 대해 알아볼 것이며, 어떤 자료구조를 선택하느냐에 따라 과정과 결과값에서 차이가 생기게 된다. (결과값만 다를 뿐, 정렬이 완료되었음은 동일하다.)

 

흐름도와 구현을 설명하기 전, 위에서 예시로 들었던 그림을 다시 가져와보자.

 

 

이를 간략히 나타내면 아래와 같이 표현할 수 있다.

 

 

간략히 나타낸 위 그래프로 흐름도와 구현 설명을 이어나가겠다.

 

진입 차수를 활용한 BFS 방식 - Queue 활용

 

1. 각 정점의 진입 차수를 계산하여 배열에 저장한다.

2. 진입 차수가 0인 정점을 Queue에 삽입한다.

3. Queue가 빌 때까지 아래 작업을 수행한다.
3 - 1. Queue의 가장 앞 요소를 pop 하여, 현재 방문 정점인 now_v에 저장한다. 
3 - 2. now_v에서 진출하는 간선으로 연결되어 해당 간선이 진입하게 되는 정점의 진입 차수를 1 감소시킨다. (now_v와 해당 정점 사이의 간선을 지운다고 생각하면 된다.)
3 - 3. 만약, 해당 정점의 진입 차수를 1 감소시켰을 때, 진입 차수가 0이 된다면 Queue에 삽입한다.

 

코드 - C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topological_sort(vector<int>* graph, int* inDegree, int N) {
	queue<int> q;
	
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) q.push(i);
	}

	int* result = new int[N];
	int now_v;
	int next_v;
	int seq = 0;

	while (not q.empty()) {
		now_v = q.front();
		q.pop();
		result[seq] = now_v;
		seq += 1;

		for (int i = 0; i < graph[now_v].size(); i++) {
			next_v = graph[now_v][i];
			inDegree[next_v]--;
			if (inDegree[next_v] == 0) q.push(next_v);
		}
	}

	for (int i = 0; i < N; i++) {
		cout << result[i] << " ";
	}
}

int main(void) {
	int N = 7;
	int* inDegree = new int[N + 1] {0} ;
	vector<int>* graph = new vector<int>[N + 1];

	graph[1].push_back(2);
	inDegree[2]++;

	graph[1].push_back(3);
	inDegree[3]++;

	graph[2].push_back(4);
	inDegree[4]++;

	graph[3].push_back(4);
	inDegree[4]++;

	graph[3].push_back(5);
	inDegree[5]++;

	graph[4].push_back(6);
	inDegree[6]++;

	graph[5].push_back(6);
	inDegree[6]++;

	graph[6].push_back(7);
	inDegree[7]++;
	
	topological_sort(graph, inDegree, N);
}

 

코드 - Python

from collections import deque

def topological_sort(graph, inDegree, N):
    result = []

    queue = deque()

    for i in range(1, N + 1):
        if inDegree[i] == 0: queue.append(i)
    
    while queue:
        now_v = queue.popleft()
        result.append(now_v)

        for next_v in graph[now_v]:
            inDegree[next_v] -= 1
            if inDegree[next_v] == 0: queue.append(next_v)
    
    for res in result:
        print(res, end=" ")

if __name__ == "__main__":
    N = 7
    inDegree = [0 for _ in range(N + 1)]
    graph = [[] for _ in range(N + 1)]
    
    graph[1].append(2)
    inDegree[2] += 1

    graph[1].append(3)
    inDegree[3] += 1

    graph[2].append(4)
    inDegree[4] += 1

    graph[3].append(4)
    inDegree[4] += 1

    graph[3].append(5)
    inDegree[5] += 1

    graph[4].append(6)
    inDegree[6] += 1

    graph[5].append(6)
    inDegree[6] += 1

    graph[6].append(7)
    inDegree[7] += 1

    
    topological_sort(graph, inDegree, N)

 

 

시작하기 앞서 진입 차수란, 특정 정점을 향해 들어오는 간선의 개수를 뜻하며 위 그림에서 4번 정점의 진입 차수는 2이다.

위상 정렬에서 중요하지는 않지만, 반대로 진출 차수란 특정 정점에서 나가는 간선의 개수를 뜻한다. 4번 정점의 진출 차수는 1이다.

 

 

inDegree 배열은 각 정점의 진입 차수(in_degree)를 저장하며, 1번째부터 7번째까지 인덱스 위치는 각각 1번 ~ 7번 정점과 매핑된다.

queue는 방문 예정인 정점들이 담길 것이다.

now_v는 현재 방문 중인 정점의 번호이며 seq는 위상 정렬의 결과인 방문 순서를 담아낼 것이다.

 

시작하기 앞서, 진입 차수가 0인 정점을 queue에 삽입한다. 위 예시에서는 1번 정점의 진입 차수가 0이기에 queue에 1을 삽입한다.

 

 

queue의 첫 번째 요소를 pop 한다.

pop한 요소는 현재 방문 중인 정점을 의미하며, now_v에 해당 정점을 저장한다.

또한 방문 순서를 저장하는 seq에도 해당 정보를 저장한다.

 

 

1번 정점에서 진출하여 진입하게 되는 정점이 존재하는지 확인한다.

2번 정점으로 진입하므로, 2번 정점의 진입 차수를 1 감소시킨다. 후에 진입 차수가 0이 되었으므로 queue에 2번 정점을 삽입한다.

 

 

추가로 3번 정점 또한 1번 정점과 연결된 간선이 진입하므로 3번 정점의 진입 차수 또한 1 감소시킨다. 후에 진입 차수가 0이 되었으므로 queue에 3번 정점을 삽입한다.

 

 

1번 정점과 연결된 모든 간선을 확인하였으므로, queue에 첫 번째 요소를 pop 하여 now_v에 해당 정점을 저장한다.

2번 정점을 방문하였으므로 seq에 해당 정보를 저장한다.

 

 

2번 정점에서 진출하여 4번 정점으로 진입하는 간선이 확인되었으므로 4번 정점의 진입 차수를 1 감소시킨다.

감소시켰으나 진입 차수가 0이 아니므로 queue에 삽입하지 않는다.

 

 

2번 정점과 연결된 간선을 모두 확인하였으므로 queue의 첫 번째 요소를 pop 하여 now_v에 저장한다.

3번 정점을 방문하였으므로 해당 정보를 seq에 저장한다.

 

 

3번 정점에서 진출하여 4번 정점으로 진입하는 간선이 확인되었으므로 4번 정점의 진입 차수를 1 감소시킨다. 후에 진입 차수가 0이 되었으므로 4번 정점을 queue에 삽입한다.

 

 

추가로 3번 정점에서 진출하여 5번 정점으로 진입하는 간선이 확인되었으므로 5번 정점의 진입 차수를 1 감소시킨다. 후에 진입 차수가 0이 되었으므로 5번 정점을 queue에 삽입한다.

 

 

3번 정점과 연결된 간선을 모두 확인하였으므로 queue의 첫 번째 요소를 pop 하여 now_v에 저장한다.

4번 정점을 방문하였으므로 해당 정보를 seq에 저장한다.

 

 

4번 정점에서 진출하여 6번 정점으로 진입하는 간선이 확인되었으므로 6번 정점의 진입 차수를 1 감소시킨다. 감소 후의 진입 차수가 0이 되지 않았으므로 queue에 삽입하지 않는다.

 

 

4번 정점과 연결된 간선을 모두 확인하였으므로 queue의 첫 번째 요소를 pop 하여 now_v에 저장한다.

5번 정점을 방문하였으므로 해당 정보를 seq에 저장한다.

 

 

5번 정점에서 진출하여 6번 정점으로 진입하는 간선이 확인되었으므로, 6번 정점의 진입 차수를 1 감소시킨다. 후에 진입 차수가 0이 되었으므로 6번 정점을 queue에 삽입한다.

 

 

5번 정점과 연결된 간선을 모두 확인하였으므로 queue의 첫 번째 요소를 pop 하여 now_v에 저장한다.

6번 정점을 방문하였으므로 해당 정보를 seq에 저장한다.

 

 

6번 정점에서 진출하여 7번 정점으로 진입하는 간선이 확인되었으므로 7번 정점의 진입 차수를 1 감소시킨다. 후에 진입 차수가 0이 되었으므로 7번 정점을 queue에 삽입한다.

 

 

6번 정점과 연결된 모든 간선을 확인하였으므로 queue의 첫 번째 요소를 pop 하여 now_v에 저장한다.

7번 정점을 방문하였으므로 해당 정보를 seq에 저장한다.

 

 

7번 정점에서 진출하는 간선이 존재하지 않는다.

모든 정점의 진입 차수가 0이 되었으므로 로직을 종료한다.

Queue 자료구조를 활용하여 위상 정렬을 한 결과는 seq와 같다.

 

진입 차수를 활용한 BFS 방식 - Stack 활용

 

사용하는 자료구조만 다를 뿐, 흐름은 같기에 그림 설명으로 대체하겠다.

 

위상 정렬은 답이 여러 개 일 수 있는 이유 중 하나이며, Queue의 FIFO 특징과 Stack의 FILO 특징 때문에 올바르게 정렬 되었음에도 방문 순서에서 조금 차이가 나게 된다.

코드 - C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void topological_sort(vector<int>* graph, int* inDegree, int N) {
	stack<int> s;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) s.push(i);
	}

	int* result = new int[N];
	int now_v;
	int next_v;
	int seq = 0;

	while (not s.empty()) {
		now_v = s.top();
		s.pop();
		result[seq] = now_v;
		seq += 1;

		for (int i = 0; i < graph[now_v].size(); i++) {
			next_v = graph[now_v][i];
			inDegree[next_v]--;
			if (inDegree[next_v] == 0) s.push(next_v);
		}
	}

	for (int i = 0; i < N; i++) {
		cout << result[i] << " ";
	}
}

int main(void) {
	int N = 7;
	int* inDegree = new int[N + 1] {0};
	vector<int>* graph = new vector<int>[N + 1];

	graph[1].push_back(2);
	inDegree[2]++;

	graph[1].push_back(3);
	inDegree[3]++;

	graph[2].push_back(4);
	inDegree[4]++;

	graph[3].push_back(4);
	inDegree[4]++;

	graph[3].push_back(5);
	inDegree[5]++;

	graph[4].push_back(6);
	inDegree[6]++;

	graph[5].push_back(6);
	inDegree[6]++;

	graph[6].push_back(7);
	inDegree[7]++;

	topological_sort(graph, inDegree, N);
}

 

코드 - Python

def topological_sort(graph, inDegree, N):
    result = []

    stack = []

    for i in range(1, N + 1):
        if inDegree[i] == 0: stack.append(i)
    
    while stack:
        now_v = stack.pop()
        result.append(now_v)

        for next_v in graph[now_v]:
            inDegree[next_v] -= 1
            if inDegree[next_v] == 0: stack.append(next_v)
    
    for res in result:
        print(res, end=" ")

if __name__ == "__main__":
    N = 7
    inDegree = [0 for _ in range(N + 1)]
    graph = [[] for _ in range(N + 1)]
    
    graph[1].append(2)
    inDegree[2] += 1

    graph[1].append(3)
    inDegree[3] += 1

    graph[2].append(4)
    inDegree[4] += 1

    graph[3].append(4)
    inDegree[4] += 1

    graph[3].append(5)
    inDegree[5] += 1

    graph[4].append(6)
    inDegree[6] += 1

    graph[5].append(6)
    inDegree[6] += 1

    graph[6].append(7)
    inDegree[7] += 1

    
    topological_sort(graph, inDegree, N)

 

초기 상태

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

시간 복잡도

 

정점의 개수가 V, 간선의 개수가 E일 때, 그래프를 위 예시들처럼 인접 리스트 방식으로 나타내면 BFS, DFS 모두 시간복잡도는 O(V + E) 이며, 만일 인접 행렬 방식으로 나타낸다면 O(V^2)의 시간복잡도를 가지게 된다.

 

 

응용 문제

 

위상 정렬 알고리즘의 템플릿 코드를 그대로 사용하여 풀 수 있는 백준 문제가 하나 있다.

 

문제 : 백준 2252번 - 줄 세우기

 

두 학생 A, B를 비교했을 때 A가 B 앞에 서야 한다면 입력값이 " A B " 로 주어진다. 즉, A -> B로 표현할 수 있다.

또한 A -> B, B -> C, C -> A 와 같은 예시로 사이클이 생길 수 없는 그래프 값이 주어진다. 왜냐하면 키 순서대로 세우는 조건에서 위와 같은 사이클이 생길 수 없기 때문!

 

전체 코드

Queue 활용

 

C++ 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topological_sort(vector<int>* graph, int* inDegree, int N) {
	int* result = new int[N] {0};

	queue<int> q;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) q.push(i);
	}

	int now_v;
	int next_v;
	int seq = 0;
	while (not q.empty()) {
		now_v = q.front();
		result[seq] = now_v;
		seq++;
		q.pop();

		for (int i = 0; i < graph[now_v].size(); i++) {
			next_v = graph[now_v][i];
			inDegree[next_v]--;
			if (inDegree[next_v] == 0) q.push(next_v);
		}
	}

	for (int idx = 0; idx < N; idx++) {
		cout << result[idx] << " ";
	}

}

int main(void) {
	int N, M;
	cin >> N >> M;

	vector<int>* graph = new vector<int>[N + 1];
	int* inDegree = new int[N + 1] {0};

	int v1, v2;
	for (int i = 0; i < M; i++) {
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		inDegree[v2]++;
	}

	topological_sort(graph, inDegree, N);

}

 

Python

from collections import deque
import sys
input = sys.stdin.readline

def topological_sort(graph, inDegree, N):
    result = []

    queue = deque()

    for i in range(1, N + 1):
        if inDegree[i] == 0: queue.append(i)
    
    while queue:
        now_v = queue.popleft()
        result.append(now_v)

        for next_v in graph[now_v]:
            inDegree[next_v] -= 1
            if inDegree[next_v] == 0: queue.append(next_v)
    
    for res in result:
        print(res, end=" ")

if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    inDegree = [0 for _ in range(N + 1)]
    
    for _ in range(M):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        inDegree[v2] += 1
    
    topological_sort(graph, inDegree, N)

 

 

Stack 활용

 

C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void topological_sort(vector<int>* graph, int* inDegree, int N) {
	int* result = new int[N] {0};

	stack<int> s;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) s.push(i);
	}

	int now_v;
	int next_v;
	int seq = 0;
	while (not s.empty()) {
		now_v = s.top();
		result[seq] = now_v;
		seq++;
		s.pop();

		for (int i = 0; i < graph[now_v].size(); i++) {
			next_v = graph[now_v][i];
			inDegree[next_v]--;
			if (inDegree[next_v] == 0) s.push(next_v);
		}
	}

	for (int idx = 0; idx < N; idx++) {
		cout << result[idx] << " ";
	}

}

int main(void) {
	int N, M;
	cin >> N >> M;

	vector<int>* graph = new vector<int>[N + 1];
	int* inDegree = new int[N + 1] {0};

	int v1, v2;
	for (int i = 0; i < M; i++) {
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		inDegree[v2]++;
	}

	topological_sort(graph, inDegree, N);

}

 

Python

import sys
input = sys.stdin.readline

def topological_sort(graph, inDegree, N):
    result = []

    stack = []

    for i in range(1, N + 1):
        if inDegree[i] == 0: stack.append(i)
    
    while stack:
        now_v = stack.pop()
        result.append(now_v)

        for next_v in graph[now_v]:
            inDegree[next_v] -= 1
            if inDegree[next_v] == 0: stack.append(next_v)
    
    for res in result:
        print(res, end=" ")

if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    inDegree = [0 for _ in range(N + 1)]
    
    for _ in range(M):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        inDegree[v2] += 1
    
    topological_sort(graph, inDegree, N)

 

---

 

후기

 

개념만 대충 알고 깊게 공부하지 않았던 알고리즘이다.

 

알고 있으면서 공부하지 않았다니... 저번 면접에서 위상 정렬 알고리즘을 질문으로 받으며 그 죗값을 치뤘다.

 

이번 기회에 다시 정리하며 복기하는 시간을 가지게 되었다.

알고리즘 개념이 크게 어렵지 않고, 그래서인지 더더욱 재밌는 알고리즘이라고 생각이 들었다.

 

이걸 왜 이제 공부했지..!!!!!!