문제: https://school.programmers.co.kr/learn/courses/30/lessons/42861
최소 신장 트리(MST)를 구하는 문제이다.
Kruskal 알고리즘을 사용해 MST를 구해보자.
def solution(n, costs):
answer = 0
costs.sort(key = lambda x: x[2])
link = set([costs[0][0]])
while len(link) != n:
for v in costs:
if v[0] in link and v[1] in link:
continue
if v[0] in link or v[1] in link:
link.update([v[0], v[1]])
answer += v[2]
break
return answer
코드 분석
costs.sort(key = lambda x: x[2]) # 가중치를 기준(index 2)으로 정렬한다
link = set([costs[0][0]]) # 시작점 노드를 추가한다
while len(link) != n: # 모든 노드를 방문하기까지 아래 코드를 반복한다.
for v in costs: # 모든 costs 값을 방문하며
if v[0] in link and v[1] in link: # 이미 최소비용으로 연결된 노드인 경우, 통과한다
continue
if v[0] in link or v[1] in link: # 연결할 수 있는 노드인 경우, 지금이 최소비용이므로 추가한다.
link.update([v[0], v[1]]) # set list에 중복 없이 값을 update
answer += v[2]
break # 값을 추가할 때 마다 다음 최소값을 찾기 위해 처음부터 탐색한다.
'코딩테스트' 카테고리의 다른 글
[Python] 프로그래머스 - 입국심사 (0) | 2023.10.18 |
---|---|
[Python] 프로그래머스 - 카펫 (0) | 2023.08.31 |
[Python] 프로그래머스 - 전화번호 목록 (0) | 2023.08.25 |
[Python] 백준 20055번 - 컨베이어 벨트 위의 로봇 (0) | 2023.08.23 |
[Python] 백준 15684번 - 사다리 조작 (0) | 2023.08.23 |