[백준 1774 파이썬] 우주신과의 교감 (골드 3, MST)

알고리즘 유형 : MST
풀이 참고 없이 스스로 풀었나요? : X

https://www.acmicpc.net/problem/1774

소스 코드(파이썬)

import sys, math
input = sys.stdin.readline

def find(x):
    if parent[x] < 0:
        return x
    
    parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    root_a = find(a)
    root_b = find(b)
    
    if root_a == root_b:
        return False
    
    if parent[root_a] < parent[root_b]:
        parent[root_b] = root_a
    elif parent[root_a] > parent[root_b]:
        parent[root_a] = root_b
    else:
        parent[root_a] = root_b
        parent[root_b] -= 1
    
    return True

N, M = map(int, input().split())
coordinates = [None]
edges = []
parent = [-1]*(N+1)

for _ in range(N):
    x, y = map(int, input().split())
    coordinates.append((x, y))
    
for node1 in range(1, N):
    for node2 in range(node1 + 1, N+1):
        x1, y1 = coordinates[node1]
        x2, y2 = coordinates[node2]
        cost = math.sqrt((x1-x2)**2 + (y1-y2)**2)
        
        edges.append((cost, node1, node2))

# 크루스칼 MST로 풀되, 문제에서 주는 이미 연결된 간선 정보들을
# union 함수로 미리 연결해준 뒤에 크루스칼을 수행해주면 된다.
for _ in range(M):
    n1, n2 = map(int, input().split())
    union(n1, n2)

edges.sort()

ans = 0
for w, n1, n2 in edges:
    if union(n1, n2):
        ans += w

print(f"{ans:.2f}")

풀이 요약

1. 크루스칼 MST로 푸는 전형적인 문제이다.

   다만 이 문제에서는 이전에 이미 연결된 간선이 여러 개 있는 상태에서 크루스칼 MST를 적용하는 문제이다.

   크루스칼 MST는 간선을 가중치 기준 오름차순 정렬 후, 모든 간선에 대해 유니온 파인드를 적용하여 최소 비용 신장 트리를 만드는 알고리즘이다.

   이 때 유니온 파인드가 노드와 노드를 연결하여 트리를 만들어가는 알고리즘이다.

   따라서, 유니온 함수로 기연결 간선 정보들을 미리 연결해준 뒤에 크루스칼 MST 알고리즘을 적용하면 된다.

배운 점, 어려웠던 점

• 처음에는 기연결 간선으로 주어진 간선 정보들을, 가중치를 0으로 설정한 뒤 MST 알고리즘을 적용하는 풀이를 생각했다. 그런데 WA가 떠서 결국 다른 사람 풀이를 참고했는데, 기연결 간선은 그냥 union으로 연결시켜준 뒤, 크루스칼 MST 알고리즘을 적용하기만 하면 끝나는 문제였다..

  MST 알고리즘 활용의 숙련도가 낮아서 그런지 저런 간단한 핵심이 눈에 안 보이나 보다. 문제를 많이 풀어봐야겠다..