알고리즘 유형 : MST
풀이 참고 없이 스스로 풀었나요? : O
https://www.acmicpc.net/problem/4386
소스 코드(파이썬)
import sys, math, heapq
input = sys.stdin.readline
INF = sys.maxsize
def find(cdn):
x, y = cdn
# 딕셔너리를 사용했기에, 임의의 노드의 부모는
# 좌표 튜플이거나, 음의 정수이다.(weighted union find에서
# 루트 노드의 parent 값은 음수이고 절댓값이 트리의 높이를 의미)
if type(parent[(x, y)]) == int and parent[(x, y)] < 0:
return (x, y)
parent[(x, y)] = find(parent[(x, y)])
return parent[(x, y)]
def union(cdn1, cdn2):
root_cdn1 = find(cdn1)
root_cdn2 = find(cdn2)
# 유니온이 실행되지 않았음을 리턴
if root_cdn1 == root_cdn2:
return False
if parent[root_cdn1] < parent[root_cdn2]:
parent[root_cdn2] = root_cdn1
elif parent[root_cdn1] > parent[root_cdn2]:
parent[root_cdn1] = root_cdn2
else:
parent[root_cdn1] = root_cdn2
parent[root_cdn2] -= 1
# 유니온이 실행되었음을 리턴
return True
n = int(input())
coordinates = [] # 좌표를 모아 둔 리스트
graph = [] # 간선 정보를 담을 리스트
total_weight = 0
for _ in range(n):
x, y = map(float, input().split())
coordinates.append((x, y))
for idx1 in range(len(coordinates)-1):
for idx2 in range(idx1+1, len(coordinates)):
x1, y1, x2, y2 = *coordinates[idx1], *coordinates[idx2]
weight = math.sqrt((x1-x2)**2 + (y1-y2)**2)
graph.append((weight, x1, y1, x2, y2))
# 모든 간선 정보를 가중치 기준 오름차순 정렬
graph.sort()
# key는 좌표 튜플, value는 부모를 의미함. 부모가 좌표 튜플일수도 있고,
# key 본인이 루트 노드일 경우, value는 음의 정수임(절댓값은 트리 높이)
parent = {}
# 처음에 모든 노드는 서로 연결되어있지 않고 스스로가 루트 노드이므로,
# -1로 value를 초기화해주기
for x, y in coordinates:
parent[(x, y)] = -1
for w, x1, y1, x2, y2 in graph:
if union((x1, y1), (x2, y2)):
total_weight += w
print(round(total_weight, 2))풀이 요약
-
모든 노드를 이어야하고 그 가중치의 합이 최소가 되어야한다 -> 전형적인 MST 문제
좌표값이 실수형이다. 프림 알고리즘 같은 경우에는 노드 하나를 MST 집합 T에 넣었을 때 그 노드의 인접 노드들을 모두 최소 힙에 넣어주는 작업을 수행하는데, 이를 위해서는 그래프 리스트를 노드의 좌표 정보로 인덱싱하는 형태로 만들어놔야한다.
그런데 그 좌표 값이 실수형이므로 인덱싱이 불가능하다. 즉, 이 문제는 크루스칼로 풀도록 하자. 크루스칼은 리스트에 간선 정보를 통째로 넣어두고, 그걸 정렬 후 하나씩 꺼내서 쓰기 때문에 좌표가 실수형이어도 딱히 상관없다. 다만 유니온 파인드에 쓰이는 parent 리스트같은 경우는, 이 문제에서는 인덱싱이 곤란하기 때문에 리스트말고 딕셔너리로 구현해야한다.
-
weighted union find를 활용한 크루스칼 MST 알고리즘으로 푼다.
우선 유니온 파인드에 앞서, parent에 딕셔너리를 할당한다. 이 후, 모든 좌표를 담는 coordinates를 순회하면서, 각각의 좌표에 대해 좌표 튜플을 키 값으로 갖고 -1을 value로 갖도록 싹 다 초기화해준다. 처음 상태에서는 모든 노드 스스로가 루트 노드이기에 -1을 할당해준 것이다. (value가 음의 정수이면, 그 좌표(key)는 루트 노드이고 트리 높이가 value의 절댓값임)
-
이 후 graph의 간선 정보를 모두 순회하면서 union-find를 실행한다.
union이 실행된 간선에 한해 total_weight에 그 간선의 가중치를 누적하여 더해준다.
union이 실행된 여부는 union 함수 내부에서 리턴 값을 조정하여 판단할 수 있다.
한편 find 함수를 구현할 때 유의할 점이 있는데, 우선 parent의 value 값으로는 두 가지가 있다. 음의 정수이거나, 좌표를 나타내는 튜플 값이거나.
튜플 값인 경우에는 인자로 들어온 좌표가 부모 노드임을 의미하고, 음의 정수인 경우는 인자로 들어온 좌표 본인이 루트 노드이며 그 절댓값이 본인이 속한 트리의 높이를 의미한다.
즉, parent 값이 음의 정수이면 본인을 그대로 리턴해주고, 그 외의 경우에는 튜플이 들어온 경우이므로 부모 노드의 parent값을 본인의 parent값에 갱신해준 후 갱신된 본인의 parent값을 리턴해주면 된다.
배운 점, 어려웠던 점
- 노드의 형태에 따라 그래프를 리스트로 나타낼 수 있는지, 딕셔너리로 나타낼 수 있는지가 달라짐을 경험할 수 있었고, 그에 따라 프림 알고리즘의 적용 여부가 달라질 수 있음을 알게되어 유익했다.
