ps:problems:programmers:42861
섬 연결하기
| ps | |
|---|---|
| 링크 | programmers.co.kr/… |
| 출처 | 프로그래머스 |
| 문제 번호 | 42861 |
| 문제명 | 섬 연결하기 |
| 레벨 | Level 3 |
| 분류 |
최소 신장 트리 |
| 시간복잡도 | O(ElogV) |
| 인풋사이즈 | V<=100, E<=5000 |
| 사용한 언어 | Python |
| 해결날짜 | 2020/11/23 |
| 태그 | |
- 아무 트릭도 없이 순수한 최소 신장 트리 (Minimum Spanning Tree / MST) 문제.
코드
"""Solution code for "Programmers 42861. 섬 연결하기".
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42861
- Solution link: http://www.teferi.net/ps/problems/programmers/42861
"""
from teflib import tgraph
def solution(n, costs):
wgraph = [{} for _ in range(n)]
for u, v, w in costs:
wgraph[u][v] = wgraph[v][u] = w
return tgraph.minimum_spanning_tree(wgraph)- Dependency: teflib.tgraph.minimum_spanning_tree
ps/problems/programmers/42861.txt · 마지막으로 수정됨: 2021/07/02 14:50 저자 teferi
토론