[백준] 1197. 최소 스패닝 트리 (Python)

백준 문제 풀이 - 최소 스패닝 트리 MST
https://www.acmicpc.net/problem/1197

📰 문제

---

문제 확인 🏃

💡 입출력 예제

---

3 3
1 2 1
2 3 2
1 3 3

>> 3

💬 풀이

---

🎵 첫번째 풀이 with Kruskal

V, E = map(int, input().split())            # 정점의 개수, 간선의 개수
parent = [num for num in range(V+1)]        # 부모 테이블

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

edges = []

for _ in range(E):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

edges.sort()
answer = 0

for edge in edges:
    cost, a, b = edge
    if find(a) != find(b):
        union(a, b)
        answer += cost

print(answer)

🎵 두번째 풀이 with Kruskal

import sys

V, E = map(int, sys.stdin.readline().split())           # 정점의 개수, 간선의 개수
parent = [num for num in range(V+1)]                    # 부모 테이블

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution():
    edges = []

    for _ in range(E):
        a, b, cost = map(int, sys.stdin.readline().split())
        edges.append((cost, a, b))

    edges.sort()
    answer = 0

    for edge in edges:
        cost, a, b = edge
        if find(a) != find(b):
            union(a, b)
            answer += cost

    print(answer)

if __name__ == '__main__':
    solution()

🎵 세번째 풀이 with Prim

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())       # 정점의 개수, 간선의 개수
graph = [[0] * (V + 1) for _ in range(V + 1)]

def prim(start):
    heap = []
    selected = [False] * (V + 1)

    heapq.heappush(heap, (0, start))
    answer = 0

    while heap:
        cost, n = heapq.heappop(heap)
        if not selected[n]:
            selected[n] = True
            answer += cost

            for i in range(1, V + 1):
                if graph[n][i] != 0 and not selected[i]:
                    heapq.heappush(heap, (graph[n][i], i))

    return answer

def solution():
    for _ in range(E):
        a, b, cost = map(int, sys.stdin.readline().split())
        graph[a][b] = graph[b][a] = cost

    print(prim(1))


if __name__ == '__main__':
    solution()

✒️ 생각

---

sys 입력방법도 계속 사용해서 익숙해져야겠어.. 😳