[백준] 4386번 별자리 만들기(크루스칼 알고리즘)(Python - 파이썬)

문제 접근

n개의 별들의 좌표를 입력 받아서 그 별들을 이어 별자리를 만들 수 있는데 별자리를 만드는데 드는 최소 비용을 구해야합니다.

별자리의 조건은 다음과 같습니다.

- 별자리를 이루는 선은 서로 다른 두별을 일직선으로 이은 형태이다.

- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별은 2차원 평면 위에 놓여있고 선을 하나 이을 때 마다 두 별 사이의 거리만큼의 비용이 든다고 합니다.

 

별자리의 조건 및 문제를 통하여 최소 신장 트리를 구해야한다는 것을 알 수 있습니다.

크루스칼 알고리즘을 사용하여 최소 신장 트리를 구하였습니다.

2022.03.06 - [정보[Information]] - 신장 트리(Spanning Tree) / 크루스칼 알고리즘(Kruskal Algorithm)(Python - 파이썬)

 

3개의 별이 주어진다면 3개의 점(x, y좌표)가 주어질 것이고 3개의 점사이의 거리를 구하고  점들 사이의 거리를 비용(간선)이라고 생각하였습니다. 

정답 코드

def findParent(parent, x) :
    if parent[x] != x:
        parent[x] = findParent(parent, parent[x])
    return parent[x]

def unionParent(parent, a, b) :
    a = findParent(parent,a)
    b = findParent(parent,b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

# 별의 개수
n = int(input())
parent = [0] * (n+1)

# 별들의 좌표가 담김
star = [(0,0)] * (n+1)
# 그래프의 정보가 담김
# (cost, a, b) 가 담기는데 a 와 b 사이의 거리가 cost라는 뜻
edge = []
result = 0

for i in range(1, n+1) :
    parent[i] = i

for i in range(1, n+1) :
    x, y = input().split()
    star[i] = (float(x), float(y))

# 별사이의 거리(cost)를 구하여 edge에 담음
for i in range(1, n+1) :
    for j in range(i+1, n+1) :
        # 점 a, b사이의 거리는
        # 점 a와 b의 x좌표의 차의 제곱 + 점 a와 b의 y좌표의 차의 제곱을 루트
        
        # 점 a, b의 x좌표 차의 제곱
        xdif = (star[j][0] - star[i][0]) ** 2
        # 점 a, b의 ㅛ좌표 차의 제곱
        ydif = (star[j][1] - star[i][1]) ** 2
        
        # 점 a, b사이의 거리
        cost = (xdif+ydif) ** 0.5
        edge.append((cost, i, j))

# 비용순으로 정렬
edge.sort()

for k in edge :
    cost, a, b = k

    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if findParent(parent, a) != findParent(parent, b):
        unionParent(parent,a, b)
        result += cost

# 소수점 둘째 자리까지만 출력해야하기 때문에 round함수를 사용
print(round(result, 2))