사용자 도구

사이트 도구


ps:problems:boj:1197

최소 스패닝 트리

ps
링크acmicpc.net/…
출처BOJ
문제 번호1197
문제명최소 스패닝 트리
레벨골드 4
분류

최소 신장 트리

시간복잡도O(ElogV)
인풋사이즈E<=100,000, V<=10,000
사용한 언어Python
제출기록49884KB / 488ms
최고기록272ms
해결날짜2021/08/03
태그

30단계

풀이

  • 문제 제목 그대로 최소 신장 트리 (Minimum Spanning Tree / MST)를 구하기만 하면 되는 문제.
  • 그래프에 음수 가중치가 있지만 따로 신경쓸 필요는 없다. Prim 알고리즘과 Kruskal 알고리즘 모두 음수 가중치의 존재여부에 관계 없이 정상적으로 동작한다.
  • 시간복잡도는 O(ElogV)

코드

"""Solution code for "BOJ 1197. 최소 스패닝 트리".

- Problem link: https://www.acmicpc.net/problem/1197
- Solution link: http://www.teferi.net/ps/problems/boj/1197

Tags: [MST]
"""

import sys
from teflib import tgraph


def main():
    V, E = [int(x) for x in sys.stdin.readline().split()]
    edges = []
    for _ in range(E):
        A, B, C = [int(x) for x in sys.stdin.readline().split()]
        edges.append((C, A - 1, B - 1))

    print(tgraph.minimum_spanning_tree_from_edges(V, edges))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q N N K​ Q
 
ps/problems/boj/1197.txt · 마지막으로 수정됨: 2021/10/24 14:19 저자 teferi