백준 1197번: 최소 스패닝 트리 python 풀이 및 정답 코드

문제 링크

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

 

문제 설명

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

 

문제 풀이

*최소 스패닝 트리(최소 신장 트리):주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 프림 알고리즘과 크루스칼 알고리즘이 있다.
*크루스칼 알고리즘: 상호배타적 집합 자료구조를 사용하는 예
*프림 알고리즘: 시작 정점에서부터 방문하지 않은 인접한 간선 중 가장 작은 가중치를 가진 간선을 선택하여 정점을 추가하는 방식이다. 그래프에서 최단 거리를 찾는 다익스크라 알고리즘과 형태가 유사함.

참고: https://www.apexcel.blog/algorithm/graph/mst/mst/

최소 신장 트리(MST, Minimun Spanning Tree)

앞전에 다익스트라를 사용했으니 프림 알고리즘으로 풀어보기로 했다.

1. 현재 정점과 인접한 정점들 중 가장 가중치가 작은 정점을 골라(힙) 방문하지 않은 정점이라면
    1-1. 방문했다고 표시하고
    1-2. 가중치를 더하고
    1-3. 정점 카운트에 1을 더한다.
    1-4. 다음 방문할 정점을 위해 간선을 힙에 넣어준다

2. 모든 정점을 순회했으면 알고리즘을 종료한다.

 

 

 

코드

import sys
from heapq import heappop, heappush

V, E = map(int, input().split())
visited = [False] * (V+1)
Es = [[] for _ in range(V+1)]
heap = [[0, 1]]

for _ in range(E):
    start, end, weight = map(int, input().split())
    Es[start].append([weight, end])
    Es[end].append([weight, start])

answer = 0
# 간선 갯수
count = 0

while heap:
    if count == V:
        break
    weight, start = heappop(heap)
    if not visited[start]:
        visited[start] = True
        answer += weight
        count += 1
        for i in Es[start]:
            heappush(heap, i)
            
print(answer)

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰