그래프 자료구조는 코딩 테스트에서 난이도가 제법 있으면서도 어려운 부분입니다.
앞서 살펴본 DFS/BFS, 최단 경로 모두 그래프 자료구조를 활용합니다. 이 외에도 다양한 그래프 자료구조를 이용한 문제들과 알고리즘이 있으며, 이들 역시 코딩 테스트에 종종 등장하므로, 반드시 알아 두어야 합니다.
이런 알고리즘은 또한 앞에서 소개한 개념에 포함되기도 합니다. 아래 소개할 크루스칼 알고리즘의 경우 그리디 알고리즘에 포함되며, 위상 정렬의 경우 큐/스택 자료구조를 잘 알고 있어야 이해할 수 있습니다.
더불어, 트리 (tree) 자료구조는 그래프 자료구조를 이용하는 다양한 알고리즘에서 사용되므로, 잘 알아 두어야 합니다.
앞서 최단 거리를 살펴볼 때 등장했던 우선순위 큐의 경우, 최대/최소 힙을 이용하는데, 힙은 이진 트리 형식을 취합니다. 트리는 컴퓨터과학 분야에서는 방향 그래프로 간주되며, 그래프와 비슷하면서도 차이가 존재합니다. 방향성, 순환성, 루트 노드 존재 여부, 노드간 관계성, 모델의 종류 등에서 차이를 보입니다.
또, 그래프는 두 가지 방법으로 구현할 수 있습니다. 배열을 사용하는 인접 행렬 방식과, 링크드 리스트를 사용하는 인접 리스트 방식이 존재하는데, 각각 탐색 시간과 메모리 차지에서 장단점을 가지고 있습니다. 우선순위 큐의 경우, 링크드 리스트를 사용하는 방식입니다. 노드의 개수 V만큼의 리스트를 만들고, 각 노드와 연결된 간선에 대한 정보를 리스트에 저장했습니다. 반면, 플로이드-워셜 알고리즘은 인접 행렬 방식을 이용합니다. V^2 크기의 2차원 배열을 만들고, 따라서 메모리를 더 사용하지만 원하는 특정 지점 (index)에 대한 탐색에서 이득을 봅니다. 이처럼 늘 메모리와 시간을 염두에 두고, 그에 걸맞는 알고리즘을 선택해야 합니다.
이 글에서는 다음 세 가지 내용에 대해 다루도록 하겠습니다:
- 서로소 집합 (disjoint sets)
- 크루스칼 알고리즘 (kruskal algorithm)과 신장 트리 (spanning tree)
- 위상 정렬 (topology sort)
서로소 집합
서로소 집합이란, 수학에서 "공통 원소가 없는 두 집합" 을 의미합니다. 예를 들어, 두 집합 A = {1, 2}, B = {3, 4}가 존재한다면, 두 집합 A와 B는 서로소 관계입니다. 반면, 집합 C = {2, 3}은 A, B 모두와 서로소 관계가 아닙니다.
서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용되므로, 꼭 알아두도록 합시다.
서로소 집합 자료구조란, 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조입니다. union, find 두 개의 연산으로 조작하게 됩니다. union (합집합)은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이며, find (찾기) 연산은 특정한 원소가 속한 집합을 찾는 연산입니다. 따라서 서로소 집합 자료구조는 union-find 자료구조라고도 부릅니다.
서로소 집합 자료구조는 기본적으로 트리 자료구조를 이용하여 구현합니다.
서로소 집합 정보 (union 연산)이 주어졌을 때, 다음 순서를 통하여 집합을 표현합니다:
- union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인합니다.
- A, B의 루트 노드 A', B'를 각각 찾습니다.
- A'를 B'의 부모 노드로 설정합니다. 즉, B'가 A'를 가리키도록 합니다.
- 모든 union 연산을 처리할 때까지 위 과정을 반복합니다.
실제로 구현할 때는 A', B' 중 원소 번호가 더 작은 쪽이 부모 노드가 되도록 구현하는 경우가 많으므로, 여기서도 마찬가지 방식을 따르도록 하겠습니다.
예시를 통해 보다 자세히 다루어 보도록 하겠습니다. 전체 집합 {1, 2, 3, 4, 5, 6}이 6개의 원소로 구성되어 있고, 이어서 union 연산이 4개 주어집니다.
- union 1, 4
- union 2, 3
- union 2, 4
- union 5, 6
위 연산이 의미하는 바는, '1과 4는 같은 집합', '2와 3은 같은 집합', '2와 4는 같은 집합', '5와 6은 같은 집합'입니다. 4개의 union 연산이 수행된 후, 전체 원소들이 어떻게 나누어지는지 살펴 봅시다.
설명을 보다 수월하게 하기 위해, 트리 구조가 아닌 그래프 구조를 이용하여 union 관계를 설명하도록 하겠습니다.
단계 0.
가장 먼저, 노드 개수 (V) 크기의 부모 테이블을 초기화합니다. 본 예시에서는 V = 6이므로, 같은 크기의 배열을 초기화합니다.
모든 원소가 자기 자신을 부모로 가지고, 따라서 6개의 트리가 개별적으로 존재하고 있다고 이해해도 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 3 | 4 | 5 | 6 |
단계 1.
union 1, 4 연산을 수행합니다. 1과 4가 합쳐지며, 이때 숫자가 더 작은 1번이 4번의 부모 노드가 됩니다. 이에 맞춰서, 부모 테이블을 갱신합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 3 | 1 | 5 | 6 |
단계 2.
union 2, 3 연산을 수행합니다. 2와 3이 합쳐지며, 이때 숫자가 더 작은 2번이 3번의 부모 노드가 됩니다. 이에 맞춰서, 부모 테이블을 갱신합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 2 | 1 | 5 | 6 |
단계 3
union 2, 4 연산을 수행합니다. 2와 4가 합쳐지며, 각각의 부모는 2, 1입니다. 따라서 2의 부모를 1로 설정하면 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 1 | 2 | 1 | 5 | 6 |
단계 4
union 5, 6 연산을 수행합니다. 숫자 5와 6이 합쳐지며, 5가 6보다 작으므로 5가 6의 부모가 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 1 | 2 | 1 | 5 | 5 |
총 4개의 union 연산이 끝났습니다. union 연산의 핵심은, 계산을 효율적으로 하기 위해, 위에서 표로 나타낸 '부모 테이블' 을 항상 가지고 있어야 한다는 점입니다.
다만, 부모 테이블은 단순히 부모 여부만을 확인해 줍니다. 예를 들어, 위 예시에서 3의 부모는 2이지만, 2의 부모는 1입니다. 따라서 최종적으로 3의 부모는 1이라고 할 수 있는데, 이를 확인하려면 늘 재귀적으로 부모를 거슬로 올라가야 합니다.
그림을 보면, 1, 2, 3, 4가 한 부분집합으로 엮였고, 5, 6이 또 다른 부분집합으로 엮여 있습니다. 1, 2, 3, 4의 루트 노드는 1이며, 5, 6의 루트 노드는 5라고 할 수 있습니다.
서로소 집합을 코드로 나타내면 다음과 같습니다.
int findParent(int x) {
if (x == parent[x]) return x;
else return findParent(parent[x]);
}
void unionParent(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x < y) parent[y] = x;
else parent[x] = y;
}
int main() {
cin >> v >> e;
//부모 테이블의 초기화: 각 노드의 부모는 자기 자신으로 초기화한다.
for (int i = 1; i <= v; i++)
parent[i] = i;
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
unionParent(a, b);
}
cout << "각 원소가 속한 집합: \n";
for (int i = 1; i <= v; i++)
cout << i << " " << findParent(i) << '\n';
cout << "부모 테이블: \n";
for (int i = 1; i <= v; i++)
cout << parent[i] << " ";
}
위 내용을 제대로 이해했다면 구현상 크게 어려운 점은 없을 것입니다. union, find 연산을 각각 구현하였고, main에서는 입력과 출력을 위한 내용을 적어 넣었습니다.
실행하면 다음과 같은 결과를 얻습니다.
원소 1~4는 집합 1에 속해 있고, 원소 5, 6은 집합 5에 속해 있다고 합니다. 그 외에도, 우리가 위 예시에서 진행한 대로 부모 테이블도 기록되 어 있는 것을 확인할 수 있습니다.
위 코드의 문제는 무엇일까요? find 함수가 다소 비효율적으로 동작한다는 것입니다. 최악의 경우, find 함수가 모든 노드를 확인해야 하며, 이 때 시간 복잡도는 O(V)가 됩니다.
이것을 어떻게 더 효율적으로 만들 수 있을까요? '경로 압축 기법 (path compression)'을 소개합니다. 경로 압축 기법이란, find 함수를 재귀적으로 호출한 뒤에, 부모 테이블값을 갱신하는 기법입니다. 코드로 직접 봅시다.
int findParent(int x_parent, int x) {
if (x != parent[x])
parent[x] = findParent(x_parent, parent[x]);
return parent[x];
}
findParent 함수를 위처럼 수정해 줍니다. 그러면, find 함수 호출 후, 해당 노트의 루트 노드가 바로 부모 노드가 됩니다. 즉, 부모 테이블을 미리 최신 상태로 갱신해 두어, find의 연산 속도를 줄이는 것입니다.
위처럼 함수를 수정하고 다시 실행해 보면, 다음의 결과를 얻습니다.
각 원소가 속한 집합이 그대로 부모 테이블에 저장되어 있는 것을 확인할 수 있습니다.
서로소 집합 알고리즘의 시간 복잡도는, 경로 압축 방법을 이용하여 구현했을 때를 기준으로, V개의 노드와 최대 V-1개의 union 연산, M개의 find 연산이 가능할 때, O(V + M(1/ log(2-(M/V)V))) 라고 합니다. 구체적인 증명은 생략하겠습니다. 복잡해 보이지만, 대략 V + M log 정도의 복잡도를 가진다고 이해하면 되겠습니다.
경로 압축 외에도 여러 방법으로 시간 복잡도를 줄일 수 있지만, 코딩 테스트에서는 이 정도만으로 충분하고, 또 크게 복잡하지 않으므로, 이 정도 선에서 마무리 하도록 하겠습니다.
알고리즘을 공부했으면 이것이 어디에 쓰이는지도 알아봐야 하겠지요.
서로소 집합 알고리즘은 다양한 알고리즘에 사용될 수 있는데, 특히 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있습니다.
(방향 그래프의 사이클은 DFS를 이용하여 판별할 수 있습니다. 이는 기회가 된다면 나중에 다루도록 하겠습니다.)
그래프의 사이클이란, 특정 노드 A에서 시작했을 때, 자기 자신으로 돌아오는 경로가 있다면 사이클이 존재한다고 합니다. union 연산은 그래프에서의 간선으로 표현될 수 있다고 했스빈다. 따라서, 간선을 하나씩 확인하여, 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하여, 사이클 유무 여부를 판별할 수 있습니다.
- 각 간선을 확인하며, 두 노드의 루트 노드를 확인합니다.
- 루트 노드가 서로 다르다면, 두 노드에 대하여 union 연산을 수행합니다.
- 루트 노드가 서로 다르다면, 사이클이 존재하는 것입니다.
- 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복합니다.
간단한 예시를 통해 알아봅시다.
단계 0.
모든 노드에 대하여, 자기 자신을 부모로 갖도록 부모 테이블을 초기화합니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 2 | 3 |
단계 1.
가장 먼저, 간선 (1, 2)를 확인합니다. 두 노드의 루트 노드가 다르므로, union 연산을 수행합니다. 1이 2보다 작으므로, 1이 2의 루트 노드가 됩니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 1 | 3 |
단계 2.
이어서, 간선 (1, 3)을 확인합니다. 두 노드의 루트 노드가 다르므로, union 연산을 수행합니다. 1이 3보다 작으므로, 1이 3의 루트 노드가 됩니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 1 | 1 |
단계 3.
마지막으로, 간선 (2, 3)을 확인합니다. 두 노드의 루트 노드가 1로, 같습니다. 따라서 사이클이 존재한다고 판단하고 탐색을 종료합니다.
| 인덱스 | 1 | 2 | 3 |
| 부모 | 1 | 2 | 3 |
위 과정을 코드로 옮겨 봅니다.
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
if (findParent(parent[a], a) == findParent(parent[b], b)) {
cycle = true;
break;
}
else
unionParent(a, b);
}
main 함수 내의 과정입니다. 이외 findParent, unionParent 등은 이전과 같습니다.
신장 트리와 크루스칼 알고리즘
신장 트리 (spanning tree)는 코딩 테스트에서 그리디 알고리즘 문제로 자주 출제되는 유형 중 하나입니다. 기본적으로 신장 트리란, 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 이 때, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하며, 이렇기 때문에 이러한 그래프를 신장 트리라고 부릅니다.
만약 위의 우측 사진 중 3-6번이 연결되여 사이클이 존재해 지거나, 1-6번이 연결이 끊긴다면 신장 트리라고 하지 않습니다.
크루스칼 알고리즘
다양한 문제 상황에서, 가능한 한 최소의 비용으로 신장 트리를 찾아야 할 때가 있습니다 (보통 간단하게 최소 신장 트리, minimum spanning tree 라고 부릅니다). 다음 예를 들어봅시다.
3개의 도시가 있고, 각 도시 사이에 도로를 건설하려고 합니다. 각 도로의 비용은 위 사진과 같습니다.
모든 도시를 연결할 때, 최소한의 비용으로 연결하려면 어떻게 해야 할까요?
위 그래프는 간단하니, 모든 경우의 수를 쉽게 파악할 수 있습니다. 도로 두 개를 건설해야 모든 노드를 연결할 수 있을 것입니다.
가능한 경우의 수는 세 가지입니다.
25 + 13 = 48, 25 + 23 = 58, 23 + 13 = 46.
즉, 1-2 (23), 2-3 (13) 을 연결하면, 총합 최소한의 비용으로 모든 도시를 연결할 수 있습니다. 이처럼 최소 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘이라고 하는데, 대표적으로 크루스칼 알고리즘 (kruskal algorithm)이 존재합니다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류됩니다.
알고리즘은 다음의 순서를 따릅니다:
- 간선 데이터를 비용에 따라 오름차순으로 정렬합니다.
- 간선을 하나씩 확인하며, 현재의 간선이 사이클을 발생시키는지 확인합니다.
- 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함시킵니다.
- 사이클이 발생하는 경우, 최소 신장 트리에 포함시키지 않습니다.
- 모든 간선에 대하여 2번 과정을 반복합니다.
예시를 통해 알아보도록 합시다.
위와 같은 그래프가 있을 때, 모든 노드를 최소한의 비용으로 연결해 봅시다. 위에서 소개한 방법대로 진행하겠습니다.
단계 0.
각 간선들의 값을 오름차순으로 정렬합니다. 무방향성 그래프이므로, 노드는 작은 순서가 왼쪽에 오도록 하여 (a, b) 형태로 적겠습니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
예시이므로, 가독성을 위해 노드 데이터 순서에 따라 나열하도록 하겠습니다. 실제로는 간선 정보를 배열에 담은 후 정렬합니다.
단계 1.
아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (3, 4)가 선택되고, 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다 (union 연산을 수행합니다).
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 1 |
단계 2.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (4, 7)이 선택되고, 4와 7은 같은 집합에 속해있지 않기 때문에 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 1 | 단계 2 |
단계 3.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (4, 6)이 선택되고, 4와 6은 같은 집합에 속해있지 않기 때문에 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 1 | 단계 3 | 단계 2 |
단계 4.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (6, 7)이 선택되고, 6과 7은 같은 집합에 속해있으므로, 추가하면 신장 트리에 사이클이 생기게 됩니다. 따라서 union 연산을 수행하지 않고 넘어갑니다. union 연산을 수행하지 않고 넘어가는 경우 순서 칸에 x 표시를 하겠습니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 1 | 단계 3 | 단계 2 | x |
단계 5.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (1, 2)가 선택되고, 1과 2는 같은 집합에 속해있지 않기 때문에 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 4 | 단계 1 | 단계 3 | 단계 2 | x |
단계 5.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (1, 2)가 선택되고, 1과 2는 같은 집합에 속해있지 않기 때문에 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 4 | 단계 1 | 단계 3 | 단계 2 | x |
단계 6.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (2, 6)이 선택되고, 2와 6은 같은 집합에 속해있지 않기 때문에 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 4 | 단계 5 | 단계 1 | 단계 3 | 단계 2 | x |
단계 7.
그 다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (2, 3)이 선택되고, 2와 3은 같은 집합에 속해있으므로, 추가하면 신장 트리에 사이클이 생기게 됩니다. 따라서 union 연산을 수행하지 않고 넘어갑니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 4 | x | 단계 5 | 단계 1 | 단계 3 | 단계 2 | x |
단계 8.
다음으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (5, 6)이 선택되고, 5와 6은 같은 집합에 속해있지 않기 때문에 이를 추가해도 사이클이 발생하지 않습니다. 따라서 이것을 집합에 포함시킵니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 4 | x | 단계 5 | 단계 1 | 단계 3 | 단계 2 | 단계 8 | x |
단계 9.
마지막으로, 아직 확인하지 않은 간선 중 가장 비용이 낮은 간선이 연결하는 노드를 선택합니다. 여기서는 (1, 5)가 선택되고, 1과 5는 같은 집합에 속해있으므로, 추가하면 신장 트리에 사이클이 생기게 됩니다. 따라서 union 연산을 수행하지 않고 넘어갑니다.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
| 순서 | 단계 4 | x | x | 단계 5 | 단계 1 | 단계 3 | 단계 2 | 단계 8 | x |
크루스칼 알고리즘이 종료된 후 얻은 최소 신장 트리는 다음과 같습니다.
위 그래프에서, 연결된 간선들의 값을 모두 더하면, 최소로 모든 도시를 연결하는 비용이 되며, 그 값은 159입니다.
이를 코드로 나타내면 다음과 같습니다. 앞서 서로소 집합에서 다룬 find, union 함수를 그대로 사용하는 점을 주목하여 읽어보세요.
for (int i = 0; i < e; i++) {
int a, b, cost;
cin >> a >> b >> cost;
edges.push_back(make_pair(cost, make_pair(a, b)));
}
sort(edges.begin(), edges.end());
for (int i = 0; i < edges.size(); i++) {
int cost = edges[i].first;
int node_a = edges[i].second.first;
int node_b = edges[i].second.second;
if (findParent(node_a) != findParent(node_b)) {
unionParent(node_a, node_b);
result += cost;
}
}
이 외 나머지 함수 부분은 앞과 동일합니다. 코드 전문 보기는 아래를 참고하세요:
크루스칼 알고리즘은, 간선의 개수가 E일 때 O(E log E)의 시간 복잡도를 가진다. 간선을 정렬하는 작업이 크루스칼 알고리즘에서 가장 오래 걸리는 작업인데, 그 정렬이 E log E의 시간이 걸립니다. 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시합니다.
위상 정렬
위상 정렬 (topology sort) 은 정렬 알고리즘의 일종입니다. "순서가 정해져 있는 일련의 작업을 수행할 때" 사용할 수 있는 알고리즘입니다. 다른 말로, "방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 정렬하는 것" 을 위상 정렬이라고 합니다.
정의만 들어서는 잘 이해가 되지 않을 수 있으니, 예시를 들어 설명해 보도록 하겠습니다.
대학 수업 수강 신청에서, 일부 과목은 다른 과목을 '선수 과목'으로써 요구합니다. 즉, 과목 B를 듣기 위해서는 과목 A를 먼저 들은 상태여야 한다는 것입니다. 이런 경우, '순서가 정해져 있는 일련의 작업을 수행한다' 고 할 수 있습니다.
구체적인 예를 들어 보겠습니다. 세 과목 '자료구조', '알고리즘', ' 고급 알고리즘' 이 있습니다. '자료구조' 는 선수 과목을 요구하지 않고, '알고리즘' 은 '자료구조' 를 선수 과목으로, '고급 알고리즘' 은 '자료구조', '알고리즘' 두 과목을 모두 선수 과목으로 요구합니다.
먼저, 진입차수 (indegree) 라는 개념을 다루겠습니다. 진입차수란, 특정한 노드로 들어오는 간선의 개수를 의미합니다. 위 그림에서, '고급 알고리즘' 은 두 개의 선수과목을 가지고 있고, 이를 나타내는 두 개의 화살표가 고급 알고리즘을 가리키고 있습니다. 즉, 그래프상에서 '고급 알고리즘' 의 진입차수는 2입니다.
이 개념을 가지고, 위상정렬 알고리즘을 소개하겠습니다.
- 진입차수가 0인 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
매우 간단한 과정입니다. 큐 (queue) 자료구조를 이용하고, 모든 원소를 방문하기 전에 큐가 비게 된다면, 사이클이 존재한다는 의미가 되기도 합니다. 하지만 여기서는 사이클이 존재하지 않음을 전제로 하고 설명하도록 하겠습니다.
단계 0.
먼저, 진입차수가 0인 노드를 큐에 넣습니다. 위 예에서는 1번 노드를 큐에 넣게 됩니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 1 | 1 | 2 | 1 | 2 | 1 |
| 큐 | (노드 1) | ||||||
단계 1
큐에 들어있는 노드 1을 꺼내고, 노드 1과 연결되어 있는 간선들을 제거합니다. 이후 노드들의 진입차수를 갱신하는데, 위 예에서는 노드 2, 5의 진입차수가 0이 됩니다. 이 두 노드들을 새롭게 큐에 넣습니다. 노드 2, 노드 5 중 어느 것을 먼저 넣어도 상관없지만, 여기서는 노드 번호가 낮은 노드를 우선해서 넣도록 하겠습니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 1 | 2 | 0 | 2 | 1 |
| 큐 | (노드 2) (노드 5) | ||||||
단계 2
큐에 들어있는 노드 2를 꺼내고, 노드 2와 연결되어 있는 간선들을 제거합니다. 이후 노드들의 진입차수를 갱신하는데, 위 예에서는 노드 3의 진입차수가 0이 됩니다. 이 노드를 새롭게 큐에 넣습니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 0 | 2 | 0 | 1 | 1 |
| 큐 | (노드 5) (노드 3) | ||||||
단계 3
큐에 들어있는 노드 5를 꺼내고, 노드 5와 연결되어 있는 간선들을 제거합니다. 이후 노드들의 진입차수를 갱신하는데, 위 예에서는 노드 6의 진입차수가 0이 됩니다. 이 노드를 새롭게 큐에 넣습니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 0 | 2 | 0 | 0 | 1 |
| 큐 | (노드 3) (노드 6) | ||||||
단계 4
큐에 들어있는 노드 3을 꺼내고, 노드 3과 연결되어 있는 간선들을 제거합니다. 이후 노드들의 진입차수를 갱신하는데, 새롭게 진입차수가 0이 되는 노드는 없으므로 아무것도 큐에 추가로 넣지 않고 진행합니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 큐 | (노드 6) | ||||||
단계 5
큐에 들어있는 노드 6을 꺼내고, 노드 6과 연결되어 있는 간선들을 제거합니다. 이후 노드들의 진입차수를 갱신하는데, 위 예에서는 노드 4의 진입차수가 0이 됩니다. 이 노드를 새롭게 큐에 넣습니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 큐 | (노드 4) | ||||||
단계 6
큐에 들어있는 노드 4를 꺼내고, 노드 4와 연결되어 있는 간선들을 제거합니다. 이후 노드들의 진입차수를 갱신하는데, 위 예에서는 노드 7의 진입차수가 0이 됩니다. 이 노드를 새롭게 큐에 넣습니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 큐 | (노드 7) | ||||||
단계 7
큐에 들어있는 노드 7을 꺼내고, 노드 7과 연결되어 있는 간선들을 제거합니다. 노드 7과 연결되어 있는 간선이 없으므로, 그냥 넘어갑니다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 진입차수 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 큐 | |||||||
큐가 비었으므로 탐색을 종료합니다. 모든 노드의 진입차수가 0이므로 사이클이 없음 또한 보여졌습니다.
위 과정 동안 큐에서 빠져나간 순서대로 출력하면, 그것이 위상 정렬의 결과가 됩니다. 위 과정에서는 노드 번호가 낮을수록 먼저 큐에 넣었지만, 결과는 사실 여러 가지 경우가 있습니다.
1 - 2 - 5 - 3- 6 - 4 - 7 이 위 예시의 결과이지만, 1 - 5 - 2 - 3 - 6 - 4 - 7 또한 위 정렬의 결과이기도 합니다.
위상 정렬을 구현한 함수는 다음과 같습니다.
void topology_sort() {
vector<int> result;
queue<int> q;
for (int i = 1; i <= v; i++) {
if (indegree[i] == 0)
q.push(i);
}
while (!q.empty()) {
int now = q.front();
q.pop();
result.push_back(now);
for (int i = 0; i < graph[now].size(); i++) {
indegree[graph[now][i]]--;
if (indegree[graph[now][i]] == 0)
q.push(graph[now][i]);
}
}
for (int i = 0; i < result.size(); i++)
cout << result[i] << " ";
}
위상 정렬은 O(V+E)의 시간 복잡도를 가집니다. 차례대로 모든 노드를 확인하며, 해당 노드에서 출발하는 간선을 차례대로 제거하기 때문입니다.
*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 2020)" 를 참고하여 작성하였습니다.
'알고리즘, 문제해결 > 알고리즘, 자료구조' 카테고리의 다른 글
| [SQL] SUM, MAX, MIN (0) | 2021.03.10 |
|---|---|
| [SQL] SELECT (0) | 2021.03.10 |
| 최단 경로 (0) | 2021.02.09 |
| 다이나믹 프로그래밍 (0) | 2021.02.05 |
| 이진 탐색 (0) | 2021.02.04 |
댓글