알고리즘 - Python / 백준 - 4386번 : 별자리 만들기

4386번: 별자리 만들기 (acmicpc.net)

4386번: 별자리 만들기

 

---

풀이

• 2차원 평면 위에 별들의 좌표가 주어지고 해당 별들을 가지고 그래프를 만들 때 거리 합의 최솟값을 구하는 문제다.
• 노드와 노드 사이 간선의 가중치가 주어지고 , 최소 거리합을 구하는 문제 이므로 최소 신장 트리 문제라고 생각했다.
• 최소 신장 트리를 푸는 방법에는 크루스칼 알고리즘 ( Kruskal Algorithm ) 과 프림 알고리즘 ( Prim Algorithm )이 존재한다.
• 프림 알고리즘이 더 익숙해 프림 알고리즘으로 문제를 해결하였다.
• 프림 알고리즘은 한점에서 부터 시작해 현재 만들어진 그래프 안에서 가장 가까운 점을 그래프에 추가하면서 전체 그래프를 만드는 알고리즘이다.
• 최소 신장 트리와 프림 알고리즘에 관한 내용은 아래 링크와 그림을 참고하자.

 

 

 

 

 

 

 

 

 

 

 

신장 부분 그래프 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

신장 부분 그래프 - 위키백과, 우리 모두의 백과사전

 

 

 

 

프림 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

 

 

 

import sys

def find_way(x1,y1,x2,y2):
    return round((((x1-x2)**2) + ((y1-y2)**2))**(1/2),2)

n = int(sys.stdin.readline())
c = []; way = [[0 for i in range(n)] for t in range(n)]
for _ in range(n):
    c.append(list(map(float, sys.stdin.readline().split(" "))))

for i in range(n-1):
    for t in range(i+1,n):
        k = find_way(c[i][0],c[i][1],c[t][0],c[t][1])
        way[i][t] = k
        way[t][i] = k

prim = [i for i in way[0]]
ans = 0

for i in range(0,n-1):
    mins = 10001;check = 0
    for k in range(0,n):
        if prim[k] > 0 and prim[k] < mins:
            mins = prim[k]
            check = k
    ans += mins
    prim[check] = 0
    for k in range(0,n):
        if prim[k] > way[check][k]:
            prim[k] = way[check][k]
print(round(ans,2))

---