[Python] 백준 - 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

 

 

문제해결방법 - 

 

 

1. 최소 스패닝 트리는 싸이클이 없으며 가중치가 최소값으로 연결된 트리 구조이다.

2. 유니온 파인드(Union Find)와 프림(Prim) 알고리즘의 방법으로 구현할 수 있다.

 

1) 유니온 파인드(Union Find)

 

자료구조 - parent리스트(자기자신을 최상위 부모 노드로 갖는 리스트), edge리스트(시작점, 도착점, 간선비용을 저장한 리스트)

FIND 함수는 parent리스트를 이용하여 최상위 부모 노드를 찾아 출력하는 함수이다.

UNION 함수는 인자 ( x ,  y )의 최상위 부모 노드를 연결시켜주는 함수이다.

 

-> edge리스트의 간선비용을 최소값부터 돌 수 있도록 정렬한 후 시작점과 끝점(최상위 부모 노드)이 연결되지 않았을 때 간선 비용을 더해준다. (연결이 되어 있다면 싸이클이기 때문에 더해주지 않고 그 전까지의 간선 비용의 합을 출력한다.)

 

2) 프림(Prim)

 

자료구조 - 다익스트라 알고리즘과 비슷하지만 dfs, bfs에서 사용하는 방문리스트와 시작점, 끝점, 간선 비용 리스트만 있으면 된다.

 

Prim 함수는 간선 비용이 최소값(Heap자료구조로 최소의 간선 비용으로만 정렬된다.)인 경우부터 진행되며, 직전 방문한 노드이거나, 싸이클이 완성되었을 시 continue로 인해 다음 코드로 진행되지 않는다.

 

 

-코드

- 유니온 파인드(Union Find)

import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())
edge, ans = [], 0
parent = [i for i in range(n+1)]
for i in range(m):
	a, b, c = map(int, input().split())
	edge.append((c, a, b))
edge.sort(key = lambda x : x[0])

def FIND(x):
	if parent[x] != x:
		parent[x] = FIND(parent[x])
	return parent[x]

def UNION(x, y):
	x = FIND(x)
	y = FIND(y)
	if x < y:
		parent[y] = x
	else:
		parent[x] = y

for i in range(m):
	c, a, b = edge[i]
	if FIND(a) != FIND(b):
		ans += c
	UNION(a, b)
print(ans)

 

- 프림(Prim)

import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
INF = sys.maxsize
v = [INF for _ in range(n+1)]
for _ in range(m):
	a, b, c = map(int, input().split())
	graph[a].append((b, c))
	graph[b].append((a, c))

def prim(start):
	q = []
	heapq.heappush(q, (0, start))
	ans, cnt = 0, 0
	while q:
		cost, idx = heapq.heappop(q)
		if v[idx] == 1:
			continue
		v[idx] = 1
		ans += cost
		cnt += 1
		for next, next_c in graph[idx]:
			if v[next] == INF:
				heapq.heappush(q, (next_c, next))
	return ans
print(prim(1))