[백준] 우주신과의 교감

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

1774번: 우주신과의 교감

1. 문제 이해

황선자씨와 연결되어 있는 우주신 네트워크에 새로운 우주신들이 추가되었습니다. 우주신들끼리 통신이 가능하므로 우주신 - 우주신, 황선자 - 우주신들간에 통로를 연결하고자 하는데 새로 만들어야 할 정신적인 통로들의 길이의 합이 최소가 되도록 해야합니다.

 

2. 문제 접근

첫번째 접근: 최소 스패닝 트리

문제를 읽자마자 최소 스패닝 트리를 구축하는 문제임을 알 수 있었습니다. 황선자씨와 다른 모든 우주신들이 연결되어야하고 이를 위해 새로 만든 통로들의 길이의 합이 최소가 되어야하기 때문입니다. 기존에 연결되어 있는 간선들은 필요한 비용이 없으므로 0으로 계산하여 넣어주고 연결되어 있지 않은 신들인 경우에는 두 좌표의 거리를 계산하여 간선의 비용으로 넣어준 다음 크루스칼을 활용하여 간단히 풀이할 수 있었습니다.

3. 풀이

import sys, math

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int ,input().split()))

isConnected = [
    [False for _ in range(n + 1)]
    for _ in range(n + 1)
]

gods = [(-1, -1)]

def getDist(p1, p2):
    x1, y1 = p1
    x2, y2 = p2

    return math.sqrt((y1 - y2) ** 2 + (x1 - x2) ** 2)

# 신들의 좌표
for _ in range(n):
    gods.append(tuple(map(int, input().split())))


# 이미 연결되어 있으면
for _ in range(m):
    a, b = tuple(map(int, input().split()))
    isConnected[a][b] = True
    isConnected[b][a] = True

# 모든 간선의 집합
edges =[]

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        # 이미 연결되어 있으면 길이가 0이다.
        if isConnected[i][j]:
            edges.append((0, i, j))
        # 연결되어 있지 않은 경우 거리를 계산해준다.
        else:
            dist = getDist(gods[i], gods[j])
            edges.append((dist, i, j))

# 가중치가 작은 간선을 기준으로 정렬
edges.sort()

parent = [x for x in range(n + 1)]

def find(p):
    if p == parent[p]:
        return p

    parent[p] = find(parent[p])
    return parent[p]

cnt = 0
ans = 0

for d, a, b in edges:

    if cnt == n - 1:
        break

    pa = find(a)
    pb = find(b)

    if pa == pb:
        continue

    cnt += 1
    ans += d

    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb

print('{:.2f}'.format(ans))

4. 회고

문제를 읽고 최소 스패닝 트리 문제임을 알 수 있어서 간단하게 풀이 할 수 있었습니다

 

5. 배운점

이 문제에서는 소수점 둘째자리까지 출력을 해야합니다. 이를 위해 파이썬의 문자열 포매팅에 대해 학습했습니다.

마지막 프린트 문처럼 {: 원하는 소수점 자리수f}.format(ans)와 같은 방식을 활용하면 소수점 자리수를 제한하여 출력할 수 있습니다.