[백준 4386번] 파이썬 - 별자리 만들기

백준 4386_별자리 만들기

시간제한 1초, 메모리 제한 128MB

# 조건

• 도현이는 우주의 신이다.
• 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
  • 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
  • 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
• 별들이 2차원 평면 위에 놓여 있다.
• 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

• 첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
• 둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다.
• 좌표는 1000을 넘지 않는 양의 실수이다.

출력

• 첫째 줄에 정답을 출력한다.
• 절대/상대 오차는 10-2까지 허용한다.

# 접근 방법

• 좌표 평면 위의 두 점 사이의 거리 공식
  • root( (x2-x1)^2 + (y2-y1)^2 )
• MST를 사용해주면 되는 문제이다.
  • 그래프의 가중치 대신 별드의 좌표가 주어진다.
  • 별들을 순회하며, (현재 별에서의 다른 별까지의 거리, 현재 별 번호, 다음 별 번호) 를 weight 리스트에 넣어준다.
• kruskal 알고리즘, find-union 알고리즘을 사용해준다.
  • n개의 점에 사이클이 생기려면 n-1개의 간선이 필요하기 때문에 cnt = n-1로 설정해준다.
• find, union의 경우
  • find => x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산
  • union => x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산
• 이미 가중치를 오름차순으로 정렬하였기 때문에, 최소비용이 보장되어 있다.

fail 코드

• 현재 별에서 모든 별이 아닌, 직전 인덱스의 별과의 거리만 계산해주어서 fail
• 경로에 대한 기초 설계를 제대로 하는 것이 중요하다!!

import sys
input = sys.stdin.readline

def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])
    return parents[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a>b:
        parents[b] = a
    else:
        parents[a] = b

n = int(input())
arr = [[*map(float, input().split())] for _ in range(n)]

arr.sort(key=lambda x:(x[0], x[1]))

parents = [i for i in range(n)]
result = 0

weight = []
cnt = n-1
for i in range(1, n):
    val = ((arr[i][0]-arr[i-1][0])**2 + (arr[i][1] - arr[i-1][1])**2)**0.5
    weight.append((val, i, i-1))

weight.sort()    
for j in weight:
    union(j[1], j[2])
    cnt -= 1

    result += j[0]
    if not cnt:
        break
print(round(result, 2))

pass

• 현재 별에서 모든 별까지의 경로를 다시 구해줌으로써 pass를 받을 수 있었다.

import sys, math  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def find(x):  
    if x != parents[x]:  
        parents[x] = find(parents[x])  
    return parents[x]  

def union(a, b):  
    a = find(a)  
    b = find(b)  
    if a>b:  
        parents[a] = b  
    else:  
        parents[b] = a  

n = int(input())  
arr = [[*map(float, input().split())] for _ in range(n)]  
edges = []  
parents = [i for i in range(n)]  
result = 0  

weight = []  
for i in range(n):  
    for j in range(i+1, n):  
        val = ((arr[i][0]-arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)**0.5  
        weight.append((val, i, j))  

weight.sort()  
cnt = n-1  
for j in weight:  
    if find(j[1]) == find(j[2]):  
        continue  
    union(j[1], j[2])  
    cnt -= 1      
result += j[0]  
    if not cnt:  
        break  
print(round(result, 2))