위상정렬.. 알고리즘을 공부하며 가장 이해가 안되었던 이름이다.
위상수학이라는 말은 들어보았지만, 위상을 정렬한다는 것은 쉽게 와닿지 않았다.
위상정렬이 무엇이며, 어떨 때 사용되는 지에 대해서 자세히 알아보자.
위상이란?
먼저 위상(Topology)이란 무엇을 말하는 것일까?
간단하게 설명하자면 그래프의 구성 형태를 의미한다.
몇 개의 노드로 이루어져 있는 지, 어떤 노드가 어떻게 연결되어 있는 지를 말한다.
예를 들어 아래의 두 그래프는 동일한 위상을 갖고 있다.
출처 : Coding ninjas
위와 같이 두 그래프가 겉보기엔 다르지만 동일한 위상을 가졌을 때
우리는 위상동형사상(Homeomorphism)이라고 한다.
위상정렬이란?
위상 정렬(Topology sorting)의 기본적인 정의는 아래와 같다.
방향이 있는 그래프의 모든 노드를 방향에 어긋나지 않게 순서대로 나열하는 것
그럼 이런 생소한 정렬 방식은 도대체 왜 사용하는 것일까?
왜 사용하는가?
보통 위상정렬은 순서가 있는 작업을 순서대로 정렬할 때에 사용된다.
예를 들어 백준 1766 - 문제집 문제를 예로 들 수 있겠다.
각 문제집에는 난이도가 정해져 있는데, 쉬운 문제를 반드시 먼저 풀어야 한다고 한다.
이렇게 일에 우선순위가 정해져 있을 때 일을 정렬할 때에 사용할 수 있다.
또한, 실제 우리 주변에서 일어날 수 있는 일을 예시로 들어보자.
아래와 같은 대학교 선수 과목을 예시로 들 수 있겠다.
어떤 과목을 듣기 위해서 반드시 먼저 들어야 하는 과목이 있을 때,
전체적인 커리큘럼에 대해 순서대로 정렬을 하고싶다면, 위상정렬을 사용할 수 있다.
생각보다 개념은 간단한 것 같다.
그렇다면 위상정렬은 어떻게 구현할 수 있을까?
위상정렬의 구현
위상 정렬은 우리가 흔히 생각하는 버블 정렬, 삽입 정렬같은 정렬과 다르다.
위의 정렬들은 단순히 원시 타입에 대한 크기를 비교하는 것이지만,
위상 정렬은 그래프의 정점에 대한 방문 순서를 정렬하는 것이다.
예를 들어 아래와 같은 유향 그래프(Direct Associated Graph)를 한 번 보자.
출처 : 안경잡이개발자
우선 그래프의 각 정점에 기록된 숫자는 방문 순서와는 관계가 없다.
그래프에서 유심히 볼 점은 6번을 진행하려면 4번을 반드시 들러야 한다는 점이다.
우선 위 그래프는 위상 정렬을 수행할 수 있는가?
그 기준은 사이클의 유무 를 확인하면 된다.
우리는 사이클이 없는 그래프에 한하여 위상정렬을 진행할 수 있다.
왜 그럴까?
사이클이 없어야 한다?
위상 정렬을 하는 이유는 일련의 작업들이 진행되어야 할 순서를 알기 위해서였다.
만약 그래프에 사이클이 존재한다고 한 번 생각해보자.
그래프를 따라서 작업을 진행한다면 사이클에 빠져서 어차피 다음으로 나아갈 수 없다.
그럼 사실 사이클이 있는 순간, 정렬을 할 이유가 없어진다고 볼 수 있다.
반대로 얘기하면, 우리는 위상 정렬을 통해 사이클의 유무를 판단할 수도 있다는 말이다.
자세한 것은 위상 정렬의 구현 방식에서 추가로 알아보도록 하자.
코드로의 구현
먼저, 위상 정렬을 수행하려면 Queue 자료구조가 필요하다.
또한 진입 차수 개념을 알고 있어야 한다.
진입 차수는 어떤 정점을 방문할 수 있는, 즉 꽂혀 있는 화살표의 수를 의미한다.
만약 진입 차수가 5인 정점이 있다면 그 정점은 5개의 정점에서 올 수 있다.
그 말은, 5개의 정점이 모두 방문을 해야 다음으로 진행할 수 있다는 말이 된다.
즉, 진입 차수가 0인 정점을 순서대로 방문하면 위상 정렬이 가능하다!
아래는 위에서 예시를 들었던, 문제집 문제의 구현 코드이다.
void topology_sort() {
priority_queue<int, vector<int>, greater<>> topo_q;
for (int i = 1; i <= vertex; i++)
if (degree[i] == 0)
topo_q.push(i); // 진입차수가 0인 노드부터 입장
while (!topo_q.empty()) {
int curr = topo_q.top();
topo_q.pop();
cout << curr << " ";
for (int i = 0; i < graph[curr].size(); i++) {
int next_node = graph[curr][i];
degree[next_node]--; // 진입차수 감소, 간선 제거의 단계
if (degree[next_node] == 0)
topo_q.push(next_node);
// 간선을 제거했을 때, 진입차수가 0이면?
// 큐에 집어넣고 진행하면 된다.
}
}
}코드를 보면, 위에서 말했던 구현 방식대로 구현이 되어있다.
진입 차수가 0인 정점을 시작점으로, 간선을 차근차근 지워나간다.
간선이 모두 지워져서 진입 차수가 0이 되는 정점을 또 방문하러 나아간다.
이 때, 사이클이 존재한다면 모든 정점을 방문하기 전에 큐가 비어버린다.
왜? 사이클이 존재하면 진입 차수가 절대 0이 될 수 없기 때문이다!
우리는 위와 같은 사실을 통해 사이클의 유무도 판별할 수 있다.