[SWEA D4] 5249. [파이썬 S/W 문제해결 구현] 7일차 - 최소 신장 트리 Python

📝 문제 설명

그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다.

0번부터 V번까지의 노드와 E개의 간선을 가진 그래프 정보가 주어질 때, 이 그래프로부터 최소신장트리를 구성하는 간선의 가중치를 모두 더해 출력하는 프로그램을 만드시오.

[입력]

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 노드번호 V와 간선의 개수 E가 주어진다.

다음 줄부터 E개의 줄에 걸쳐 간선의 양 끝 노드 n1, n2, 가중치 w가 차례로 주어진다.

1<=T<=50, 1<=V<=1000, 1<=w<=10, 1<=E<=1000000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

🚩 해결 방안

일단 프림 알고리즘을 사용하였습니다.

가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘

1. 그래프의 입력값을 상호관계를 모두 따져 dictionary에 저장
2. 이미 연결된 노드를 저장할 connected_node를 만듦.
3. 0번째 노드 부터 시작할 것이기 때문에 0번째 노드와 연결된 리스트를 heapify하여 우선순위 큐로 만든다.
4. 우선순위 큐는 pop하면 가장 작은 값이 나오기 때문에 0번 노드와 연결된 노드중 가장 작은 가중치 값 weight를 더할 수 있다.
5. 가장 작은 가중치 값인 노드를 새로운 기준 노드로 삼아 해당노드와 연결된 모든 노드를 따지되 아직 연결이 안된 노드만 따진다.
6. 우선순위 큐가 비어있을 때까지 계속 반복...

✔ 문제풀이

# 우선순위 큐를 활용한 프림 알고리즘 사용

from heapq import *
from collections import defaultdict

T = int(input())

for test_case in range(1, T + 1):
    result = 0
    V, E = map(int, input().split())
    my_graph = defaultdict(list)
    for _ in range(E):
        n1, n2, w = map(int, input().split())
        my_graph[n1].append((w, n2))
        my_graph[n2].append((w, n1))

    connected_node = set([0])
    cand_edge = my_graph[0]
    heapify(cand_edge)

    while cand_edge:
        weight, node = heappop(cand_edge) # 최소 우선순위 큐로 최소값 찾기
        if node not in connected_node:
            connected_node.add(node)
            result += weight #가중치 더해주기

            for edge in my_graph[node]: # node의 연결된 모든 node값들을 저장
                if edge[1] not in connected_node:
                    heappush(cand_edge, edge)

    print(f'#{test_case} {result}')