PY-L4-001 / 고급 그래프
최소 신장 트리
고급문제
n개 노드의 무방향 가중 간선 edges=[a,b,w]를 받습니다. 최소 신장 트리 비용을 반환하고, 전체 연결이 불가능하면 -1을 반환하세요. n은 1 이상입니다.
solve(*args) 함수에서 값을 반환하세요. print 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: [3,[[0,1,4],[1,2,2],[0,2,9]]] 반환: 6
예제 2
입력: [3,[[0,1,1]]] 반환: -1
힌트
작은 간선부터 선택하면서 순환을 만들지 않는지 검사하세요.
해설·정답 보기
Kruskal 알고리즘과 서로소 집합을 사용합니다. 선택한 간선이 n-1개인지 확인해야 합니다.
def solve(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = used = 0
for a, b, w in sorted(edges, key=lambda e: e[2]):
a, b = find(a), find(b)
if a != b:
parent[a] = b
total += w
used += 1
return total if used == n - 1 else -1solution.py결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.