1774번: 우주신과의 교감
문제 링크: 1774번: 우주신과의 교감
개요
최소 스패닝 트리(Minimum Spanning Tree, MST)는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 다시 말하면 n개 노드가 있을 때, n-1개 간선만을 이용해 가장 적은 가중치로 모든 노드를 연결하는 것이다.
이 문제에서 황선자씨가 모든 우주신들과 교감할 수 있도록 정신적 통로들을 만들어줘야 하므로, 최소 스패닝 트리를 구하는 알고리즘을 그대로 적용하여 풀이할 수 있다.
최소 스패닝 트리를 구하는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 노드에 비해 간선의 개수가 적은 경우엔 크루스칼 알고리즘이, 간선의 개수가 많은 경우에는 프림 알고리즘이 더 효율적이다. 이 문제는 사실상 모든 정점이 다른 정점과 연결된 간선이 있는 것과 마찬가지이기 때문에 프림 알고리즘이 효율적일 수 있지만, 나는 효율성과 별개로 크루스칼 알고리즘을 이용해 풀이했다.
크루스칼 알고리즘
크루스칼 알고리즘의 전체 흐름은 다음과 같다.
- 간선들을 가중치에 대해 오름차순으로 정렬한다.
- 간선들을 순서대로 탐색하며 해당 간선의 두 노드가 현재 연결되어 있지 않다면 간선을 선택하고 아니면 건너뛴다.
- 모든 간선에 대해 해당 작업을 반복하여 총 n-1개의 간선이 선택된 상태에서 마무리한다.
여기서 두 노드가 연결되어 있는지 확인하기 위해 Union-Find 알고리즘을 이용했다.
풀이
전처리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//n개 노드 좌표 입력
for (int i = 1; i <= n; i++) {
scanf("%d %d", &posX[i], &posY[i]);
parent[i] = i;
}
//입력받은 좌표로 nC2개 간선 생성
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
edges[edgesCnt].node1 = i, edges[edgesCnt].node2 = j;
edges[edgesCnt].dist = pow(posX[i] - posX[j], 2) + pow(posY[i] - posY[j], 2);
edgesCnt++;
}
}
//dist 오름차순으로 간선 정렬
qsort(edges, edgesCnt, sizeof(edges[0]), compare);
배열 posX와 배열 posY에 n개 노드의 x좌표와 y좌표를 각각 입력받은 후, nC2개 간선(노드 개수가 n개이므로 그 중 2개를 선택하는 경우의 수는 nC2)을 생성해 구조체 배열 edges에 저장한 후, 가중치(이 문제에서는 평면상에서의 거리)에 대해 오름차순 정렬한다.
Union-Find
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//조상 노드 찾기
int getRoot(int parent[MAX_N + 1], int node) {
if (parent[node] == node) return node;
parent[node] = getRoot(parent, parent[node]);
return parent[node];
}
//두 노드 union하기
void unionNode(int parent[MAX_N + 1], int node1, int node2) {
int root1 = getRoot(parent, node1);
int root2 = getRoot(parent, node2);
if (root1 < root2) parent[root2] = root1;
else parent[root1] = root2;
return;
}
두 노드가 연결되어 있는지를 알기 위해 두 노드의 조상 노드가 같은지를 확인한다는 것이 크루스칼 알고리즘에서 Union-Find를 이용하는 기본 아이디어이다.
연결된 노드 중 번호가 작은 노드를 부모 노드로 가정하여 Union-Find를 진행한다. parent[n]은 n번 노드의 부모 노드 중 하나가 들어있으며, 그것이 항상 조상 노드라는 보장은 없다.
getRoot 함수는 parent 배열을 이용해 조상 노드를 반환한다. getRoot(parent, n)을 호출하면 n번 노드에서 조상 노드까지 가기 위해 재귀를 타고 거치는 모든 노드들(k1, k2 …)에 대해 parent[k1], parent[k2]…가 해당 노드의 조상 노드로 업데이트된다. 따라서 다음번에 그 노드의 조상 노드를 찾아야 할 때 시간을 단축할 수 있다.
unionNode에서는 두 노드를 연결시킨다(조상 노드를 같게 한다). 두 노드의 조상 노드 root1과 root2를 각각 구하고, 두 조상 중 번호가 큰 노드를 v, 번호가 작은 노드를 u라고 하겠다. 원래 u의 자식이었던 노드들에게는 아무 변화가 없다. 그러나 v의 자식이었던 노드들은 다음번에 getRoot의 인자로 넣어 호출하면 v까지 타고 올라간 후, parent[v]에 할당된 u가 해당 노드의 조상 노드로 업데이트된다.
최소 스패닝 트리 만들기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//이미 연결된 것으로 주어지는 노드 union
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
unionNode(parent, u, v);
}
//크루스칼 알고리즘으로 최소 스패닝 트리 만들기
for (int i = 0; i < edgesCnt; i++) {
if (getRoot(parent, edges[i].node1) != getRoot(parent, edges[i].node2)) {
sumDist += sqrt(edges[i].dist);
unionNode(parent, edges[i].node1, edges[i].node2);
}
}
이 문제에서는 이미 m개 간선으로 노드들이 연결되어있으므로 해당 노드들에 대해 unionNode를 진행해준다.
그 후 가중치에 대해 오름차순으로 정렬된 간선들을 탐색한다. 두 노드의 조상 노드가 같은 경우 이미 연결된 노드들이므로 건너뛰고, 조상 노드가 다른 경우에만 unionNode를 진행하며 우리가 구해야 하는 가중치 총합에 해당 간선 가충지를 누적하면 완료이다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cmath>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_N 1000
typedef struct edge {
int node1, node2;
long long dist;
} Edge;
int compare(const void *a, const void *b);
int getRoot(int parent[MAX_N + 1], int node);
void unionNode(int parent[MAX_N + 1], int node1, int node2);
int main() {
int n, m, parent[MAX_N + 1];
double sumDist = 0;
int posX[MAX_N + 1], posY[MAX_N + 1], edgesCnt = 0;
Edge edges[MAX_N * MAX_N];
scanf("%d %d", &n, &m);
//n개 노드 좌표 입력
for (int i = 1; i <= n; i++) {
scanf("%d %d", &posX[i], &posY[i]);
parent[i] = i;
}
//입력받은 좌표로 nC2개 간선 생성
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
edges[edgesCnt].node1 = i, edges[edgesCnt].node2 = j;
edges[edgesCnt].dist = pow(posX[i] - posX[j], 2) + pow(posY[i] - posY[j], 2);
edgesCnt++;
}
}
//dist 오름차순으로 간선 정렬
qsort(edges, edgesCnt, sizeof(edges[0]), compare);
//이미 연결된 것으로 주어지는 노드 union
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
unionNode(parent, u, v);
}
//크루스칼 알고리즘으로 최소 스패닝 트리 만들기
for (int i = 0; i < edgesCnt; i++) {
if (getRoot(parent, edges[i].node1) != getRoot(parent, edges[i].node2)) {
sumDist += sqrt(edges[i].dist);
unionNode(parent, edges[i].node1, edges[i].node2);
}
}
printf("%.2lf", sumDist);
return 0;
}
//qsort를 위한 비교 함수
int compare(const void *a, const void *b) {
if (((Edge *)a)->dist > ((Edge *)b)->dist) return 1;
else return -1;
}
//조상 노드 찾기
int getRoot(int parent[MAX_N + 1], int node) {
if (parent[node] == node) return node;
parent[node] = getRoot(parent, parent[node]);
return parent[node];
}
//두 노드 union하기
void unionNode(int parent[MAX_N + 1], int node1, int node2) {
int root1 = getRoot(parent, node1);
int root2 = getRoot(parent, node2);
if (root1 < root2) parent[root2] = root1;
else parent[root1] = root2;
return;
}