백준 1774번: 우주신과의 교감 (Python)

접근

최소 스패닝 트리(MST) 해결 방법 중 Kruskal MST 알고리즘을 이용하여 문제를 해결하였다.

MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python)

백준 1197번: 최소 스패닝 트리 (Python)

제대로 구현한 것 같은데 인덱스 에러가 계속 떠서 오래 고민했는데 역시 문제를 열심히 봐야겠다는 생각이 들었다. m개의 이미 연결된 간선이 주어질 때 싸이클을 이루는지 검사하는 과정을 빼먹고 모두 union 하는 바람에 인덱스에러가 난 것이었다.

결론적으로는 이전의 별 연결문제와 동일하게 풀되, 이미 연결된 간선들을 체크하여 미리 union 해주면 된다. 이전 문제와 다르게 소수점 둘째자리까지 무조건 표시해야 한다는 점에서 조금 표현을 다르게 해줄 필요가 있다.

별자리 만들기 문제: 2021.05.02 - [코딩/백준 (Python)] - 백준 4386번: 별자리 만들기 (Python)

백준 4386번: 별자리 만들기 (Python)

코드

import sys
import heapq


def distance(x, y):
    return ((x[0] - y[0]) ** 2 + abs(x[1] - y[1]) ** 2) ** 0.5


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


def union(x, y):
    if parent[x] < parent[y]:
        parent[x] += parent[y]
        parent[y] = x
    else:
        parent[y] += parent[x]
        parent[x] = y


n, m = map(int, sys.stdin.readline().split())
parent = [-1 for _ in range(n + 1)]
lines = []
stars = [[]]
for i in range(1, n + 1):  # 별들을 stars에 저장
    a, b = map(int, sys.stdin.readline().split())
    stars.append([a, b])
cnt = n - 1
for i in range(m):  # 이미 연결된 간선들을 입력받아 싸이클을 이루는지 체크한 후, 간선의 개수 카운트
    a, b = map(int, sys.stdin.readline().split())
    ar, br = find(a), find(b)
    if ar != br:
        union(ar, br)
        cnt -= 1
for i in range(1, n):
    for j in range(i + 1, n + 1):
        d = distance(stars[i], stars[j])
        heapq.heappush(lines, [d, i, j])
ans = 0
while cnt:
    d, a, b = heapq.heappop(lines)
    ar, br = find(a), find(b)
    if ar != br:  # 주어진 두 별을 추가했을 때 싸이클을 이루지 않을 경우 union 해주고 카운트
        union(ar, br)
        ans += d
        cnt -= 1
print("%.2f" % ans)  # 소수점 둘째자리까지 표시

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!