[BOJ/python]4386

백준 4386 - 별자리 만들기
파이썬 풀이 입니다

---

어떻게 풀이?

일단 주어진 모든 정점을 연결하는 부분 그래프 중 그 가중치 값이 최소인 트리를 구하는 것이므로 최소 스패닝 트리 문제라고 생각을 할 수 있다

다만 이번에는 모든 노드들이 연결되어있다고 가정을 하고 진행을 하면 됐다

처음에는 그냥 Prime MST 알고리즘을 사용할 것 없이 가중치가 적은 것들끼리만 연결하면 되지 않을까 하여 다음과 같이 코드를 짰다

from collections import defaultdict
import heapq

def solution():

    N = int(input())
    S = []
    h = [] #dist, node1, node2
    answer = 0

    for _ in range(N):
        S.append(list(map(float, input().split())))
    
    for i in range(N):
        for j in range(N):
            if i != j:
                dist = ((S[i][0] - S[j][0]) ** 2 + (S[i][1] - S[j][1]) ** 2) ** 0.5
                heapq.heappush(h, [dist, i, j])
                heapq.heappush(h, [dist, j, i])
    
    visited = defaultdict(bool)

    while h:
        dist, node1, node2 = heapq.heappop(h)

        if (not visited[node1]) or (not visited[node2]):
            answer += dist
            visited[node1], visited[node2] = True, True
    
    print(round(answer, 2))

solution()

하지만 위와 같이 짰을 때 아래 그림과 같이 모든 그래프가 연결되지 않는 문제가 있었다

그래서 Prime MTS 알고리즘을 이용해 다시 작성했다

코드

from collections import defaultdict
import heapq

def solution():

    N = int(input())
    S = []
    C = defaultdict(list)
    answer = 0

    for _ in range(N):
        S.append(list(map(float, input().split())))
    
    for i in range(N):
        for j in range(N):
            if i != j:
                dist = ((S[i][0] - S[j][0]) ** 2 + (S[i][1] - S[j][1]) ** 2) ** 0.5
                C[i].append([dist, j])
                C[j].append([dist, i])
    
    heap = []
    visited = defaultdict(bool)

    heapq.heappush(heap, [0, 0])

    while heap:
        dist, node = heapq.heappop(heap)

        if not visited[node]:
            answer += dist
            visited[node] = True
        else:
            continue

        for next in C[node]:
            if not visited[next[1]]:
                heapq.heappush(heap, next)

    
    print(round(answer, 2))

solution()

• 모든 정점간의 거리를 구하고 그 정보를 저장한다
• 우선순위 큐에 첫번째 노드에 대한 정보를 넣는다(가중치, 노드정보)
• 우선순위 큐에서 가중치가 적은 순으로 [가중치, 노드] 정보를 빼며 현재 노드에 방문한 적이 없다면 answer에 가중치 값을 더하고 현재 노드 방문 체크를 한다
• 다음 노드에 대해서 방문한 적이 없다면 우선순위 큐에 [가중치, 다음노드] 정보를 추가한다

---

요즘 뭔가 알고리즘을 안 풀어서 그런가 아니면 그냥 아무 생각 없이 회사를 다녀서 그런지는 몰라도
머리가 굳은 것 같다

아님 공부를 위한 절대적인 시간이 부족해져서
핑계대고 놀고 싶어진걸지도..

앞으로는 알고리즘도 꾸준히 풀고
다른 공부도 계속 열심히 해야지✍️