[백준] 1197. 최소 스패닝 트리/Python - Gold4

❓문제

https://www.acmicpc.net/problem/1197

성능 요약

Kruskal, Python3➡️메모리: 57288 KB, 시간: 264 ms
Prim, PyPy3➡️메모리: 129144 KB, 시간: 380 ms

분류

최소 스패닝 트리, 그래프 이론

문제 설명

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

✍🏻풀이

2024.11.29 - [Computer Science/Algorithms] - [Algorithms] 최소 신장 트리 (Minimum Spanning Tree)

[Algorithms] 최소 신장 트리 (Minimum Spanning Tree)

최소 신장 트리는 위 내용과 같이 크루스컬 알고리즘과 프림 알고리즘을 사용해 구현할 수 있습니다.

크루스컬 알고리즘은 Union-Find를 이용하면 됩니다. 그리고 프림 알고리즘은 아래 사이트를 참고했습니다.

https://daegwonkim.tistory.com/191

[Python] BOJ / 1197번 / 최소 스패닝 트리

💻코드

Kruskal's Algorithms

import sys

input = sys.stdin.readline

V, E = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(E)]
parent = [v for v in range(V+1)]
edges.sort(key= lambda x: x[2])
cost = 0

def find(x): # 특정 원소가 어느 그룹에 속하는지 찾기.
    if parent[x] != x:
        return find(parent[x])
    return x

def union(a, b): # 두 그룹을 하나로 합치기.
    pA, pB = find(a), find(b)
    if pA > pB:
        parent[pA] = pB
    else:
        parent[pB] = pA

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

Prim's Algorithms

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
INF = 1e9

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [0] * n

for _ in range(m):
    a, b, c = map(int, input().split())
    edges[a - 1].append((c, b - 1))
    edges[b - 1].append((c, a - 1))

ans = 0
q = [(0, 0)]

while q:
    c, v = heappop(q)

    if not visited[v]:
        visited[v] = 1
        ans += c

        for c, u in edges[v]:
            if not visited[u]:
                heappush(q, (c, u))

print(ans)

📍후기

처음에는 크루스컬 알고리즘을 사용해서 풀었는데 PyPy3는 recursion limit를 10^6으로 설정하면 메모리를 초과하여 Python3로만 가능하다. 그러나 삼성은 PyPy3로 사용하기 때문에 프림 알고리즘으로 다시 해보았더니 프림은 PyPy3에서 가능하다.