백준 문제 풀이 - 최소 스패닝 트리 MST
⭐️파이썬 알고리즘 스터디 공통 문제⭐️
📰 문제
문제 확인 🏃
💡 입출력 예제
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8
>> 23💬 풀이
🎵 첫번째 풀이 with Kruskal
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
N = int(input()) # 컴퓨터의 수
M = int(input()) # 연결할 수 있는 선의 수
parent = [num for num in range(N+1)]
edges = []
for _ in range(M):
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(parent, a) != find(parent, b):
union(parent, a, b)
answer += cost
print(answer)
🎵 두번째 풀이 with Prim
import heapq
V = int(input()) # 노드 개수
E = int(input()) # 간선 개수
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
for _ in range(E):
a, b, cost = map(int, input().split())
Graph[a][b] = Graph[b][a] = cost
print(prim(1))
🎵 세번째 풀이 with Kruskal
입력 방법을 변경
import sys
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
N = int(sys.stdin.readline()) # 컴퓨터의 수
M = int(sys.stdin.readline()) # 연결할 수 있는 선의 수
parent = [num for num in range(N+1)]
edges = []
for _ in range(M):
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(parent, a) != find(parent, b):
union(parent, a, b)
answer += cost
print(answer)
🎵 네번째 풀이 with Kruskal
solution() 생성
import sys
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def solution():
N = int(sys.stdin.readline()) # 컴퓨터의 수
M = int(sys.stdin.readline()) # 연결할 수 있는 선의 수
parent = [num for num in range(N+1)]
edges = []
for _ in range(M):
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(parent, a) != find(parent, b):
union(parent, a, b)
answer += cost
print(answer)
if __name__ == "__main__":
solution()
✒️ 생각
간단히 풀 수는 있지만, 효율적으로 푸는 방법은 또 따로 있는 듯..😟 어떻게 풀어야 Python3으로도 빠른 속도가 나오지..
와우, 더 성능 좋은 입력 방법이 있는 줄은 알았지만 이렇게까지 차이날 줄은 몰랐다. 알고리즘 스터디 팀원이 알려줌..ㅎ sys 입력방법과 solution 함수를 사용하면 더 빨라진다ㅏ😆
🐥 Backend Developer 🐥