[Python] 프로그래머스. 섬 연결하기 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기 | 프로그래머스

 

Greedy 알고리즘 중 하나로, 그래프의 정점을 최소 비용으로 연결하는 알고리즘인 '크루스칼 알고리즘' 문제유형이다.

 

 

 

 

	import math
	def solution(n, costs):
	# 정렬했을 때 weight 가중치 작을수록 리스트 전면에 오도록 costs를 변경한다.
	costs = [(w, f, t) for f, t, w in costs]
	costs.sort()
	result = 0
	# 이미 방문한 노드는 저장한다.
	visited = set()
	# 가장 가중치 작은 것부터 연결한다
	w, f, t = costs[0]
	# 자기 자신을 연결하는 게 아니면, 첫 번째 노드 weight를 result에 저장한다.
	if f != t:
	result += w
	# 두 노드가 연결되었으므로 두 노드를 visited에 저장한다.
	visited.update([f,t])
	# 모든 노드가 연결될 때까지 반복한다.
	while len(visited) != n:
	# 연결할 수 있는 노드 weight의 최솟값을 찾아야 한다.
	_min = math.inf
	for w, f, t in costs:
	# from과 to 두 개의 노드 중 하나는 visited에 있어야 한다.
	# 즉 이미 연결된 노드들 중 하나여야 한다.
	if t in visited or f in visited:
	# 이미 둘 다 visited에 있으면,
	# 새로 들어온 weight는 기존에 연결된 두 노드의 weight보다 작을 수 없다.
	# from과 to가 같은 노드면 저장할 이유가 없음.
	if (f in visited and t in visited) or f == t:
	continue
	# weight가 가장 작은 노드로 _min값을 업데이트한다.
	if _min > w:
	_min = w
	frm, to = f, t
	# 최소 weight를 result값에 더한다.
	result += _min
	# 새로 연결한 두 개의 노드를 visited에 업데이트한다.
	visited.add(frm)
	visited.add(to)
	# while문을 빠져나오면, 모든 노드는 연결된 상태고
	# 각 노드를 연결하는 weight는 작은 순서대로 전부 찾은 상태.
	return result

view raw [프로그래머스] 섬 연결하기.py hosted with ❤ by GitHub