[BaekJoon] 1197번 : 최소 스패닝 트리

1197번 : 최소 스패닝 트리

아직 그래프 탐색 알고리즘에 대해 정확히 알지 못 한다는 사실을 알게 되었다..

프로그래머스 스킬 체크 레벨 3 을 푸는데 최소 신장 트리를 만들지 못해 탈락했다.

어떤 문제의 유형에서 최소 신장 트리를 만들어야 하냐면 그래프 내의 모든 정점을 최단거리로 잇고 싶은 경우 만든다.

MST 를 만드는 알고리즘은 두 가지가 있는데 크루스칼, 프림 알고리즘이 있다.

간선의 개수가 노드의 개수보다 많은 경우 프림을 사용한다.

이 문제에서는 크루스칼을 사용했다.

크루스칼은 사이클을 만들지 않으면서 가장 작은 무게를 가진 간선을 계속 연결시켜 나가는 것이다.

처음에는 사이클 판별을 리스트로 했다가 시간초과가 발생해 사전으로 처리 해주었다.

---

import sys


def solution():
	global edge_info
	edge_info.sort(key=lambda x: x[2])
	answer = 0
	connection = {i: 0 for i in range(1, V + 1)}
	connection[1] = 1
	connection_len = 1

	while connection_len != V:
		for idx, edge in enumerate(edge_info):
			if connection[edge[0]] >= 1 and connection[edge[1]] >= 1:
				continue

			if connection[edge[0]] >= 1 or connection[edge[1]] >= 1:
				answer += edge[2]
				connection_len += 1
				connection[edge[0]] += 1
				connection[edge[1]] += 1
				edge_info.pop(idx)
				break

	return answer


if __name__ == "__main__":
	V, E = map(int, input().split())
	edge_info = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(E)]

	print(solution())