[BOJ] 백준 4386번 문제 풀이 (Python)

1. 풀이

n개의 별들을 모두 잇는 별자리들 중 최소비용의 별자리를 찾는 문제이다. 각 별들을 노드라고 생각하고 별자리를 트리라고 생각하면 결국 최소 스패닝 트리를 찾는 문제라고 볼 수 있다.

union-find와 크루스칼 알고리즘을 사용하여 문제를 풀었다.

• union-find: disjoint set 자료구조. 조금 더 자세히 말하자면 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조라고 볼 수 있다. union 연산, find 연산으로 이루어져 있기 때문에 union-find 자료구조라고 부른다.
  • find: 어떤 원소가 주어졌을 때 어떤 집합에 속했는지 찾는 연산.
  • union: 서로 다른 집합을 합칠 때 사용하는 연산.
• 크루스칼 알고리즘: 최소 스패닝 트리를 구하는 알고리즘. 그래프의 모든 간선을 정렬한 다음 최소 간선부터 사이클이 발생하지 않는다면 트리에 포함시킨다. 사이클인지 아닌지 판별할 때 union-find를 사용한다.
  • 트리에 포함된 노드 집합을 A라하자.
  • 새로 트리에 포함시키려는 간선의 노드가 이미 A에 포함되어있다면 사이클이 발생할 것이다. 따라서 find 연산을 이용해 간선의 노드가 A에 포함되어 있는지 확인하고 없다면(사이클이 발생하지 않는다면) 간선의 노드를 union 연산을 이용해 A에 포함시킨다.

이와 같은 방식을 사용하여 최소 비용을 가진 별자리를 구하였다.

import sys
def input(): return sys.stdin.readline().rstrip()

def find_parent(a):
    if parent[a] != a:
        parent[a] = find_parent(parent[a])
    return parent[a]

def union(a,b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n = int(input())
node = { i:tuple(map(float, input().split())) for i in range(n)} 
parent = [i for i in range(n)]
edges = []
for i in range(n):
    x1,y1 = node[i]
    for j in range(i+1,n):
        x2,y2 = node[j]
        dist = ((x1-x2)**2 + (y1-y2)**2)**(1/2)
        edges.append((i,j,dist))
edges.sort(key=lambda x: x[2])
result = 0
for a, b, cost in edges:
    parent_a, parent_b = find_parent(a), find_parent(b)
    if parent_a != parent_b:
        result += cost
        union(a,b)
print(result)