문제
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
알고리즘
1. 크루스칼 알고리즘 (Kruskal's Algorithm)
그래프의 모든 정점을 최소 비용으로 연결하는 최소 스패닝 트리를 찾는 알고리즘
탐욕적인(greedy) 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구함
작동 방식
- 초기화: 시작할 때 모든 정점을 독립적인 집합으로 만든다.
- 간선 선택: 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
- 간선 연결: 가장 가중치가 작은 간선부터 선택하여 현재의 트리(T)에 추가한다. 단, 사이클을 형성하는 간선은 추가하지 않는다.
- 사이클 형성 여부는 Union-Find 알고리즘을 사용해서 확인한다.
- 모든 정점이 하나의 집합(트리)에 포함될 때까지 3번 과정을 반복한다.
Union-Find 알고리즘
크루스칼 알고리즘에서는 Union-Find 알고리즘을 사용하여 두 정점이 같은 집합에 속하는지(즉, 사이클을 형성하는지) 판별합니다.
- Find: 특정 원소가 속한 집합을 찾는다.
- Union: 두 개의 원소가 속한 집합을 합친다.
구현 코드
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
rootA = find(parent, a)
rootB = find(parent, b)
if rootA < rootB:
parent[rootB] = rootA
else:
parent[rootA] = rootB
V, E = map(int, input().split())
# 간선 정보 입력받기
edges = []
for _ in range(E):
a, b, w = map(int, input().split())
edges.append((w, a, b))
# 간선을 가중치 순으로 정렬
edges.sort()
# 각 노드에 대한 부모 테이블 초기화
parent = [i for i in range(V+1)]
# 크루스칼 알고리즘 수행
result = 0
for edge in edges:
w, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find(parent, a) != find(parent, b):
union(parent, a, b)
result += w
print(result)2. 프림 알고리즘 (Prim's Algorithm)
그래프에서 최소 스패닝 트리를 찾는 알고리즘 중 하나로, 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방식
작동 방식
- 초기화: 시작 정점만을 MST(Minimum Spanning Tree)의 집합에 포함시킨다.
- 연결 간선 선택: 현재 MST 집합 외의 정점과 연결된 간선 중, 가장 가중치가 작은 간선을 선택한다.
- 정점 추가: 해당 간선에 연결된 정점을 MST 집합에 추가한다.
- 그래프의 모든 정점이 MST 집합에 포함될 때까지 2-3의 과정을 반복한다.
구현 코드
import heapq
def prim(graph, start):
visited = [False] * len(graph)
edges = []
total_weight = 0
# 시작 노드의 연결된 간선 정보를 우선순위 큐에 추가
heapq.heappush(edges, (0, start))
while edges:
weight, current = heapq.heappop(edges)
# 이미 연결된 노드인 경우 스킵
if visited[current]:
continue
visited[current] = True
total_weight += weight
for next_node, w in graph[current]:
if not visited[next_node]:
heapq.heappush(edges, (w, next_node))
return total_weight
# 입력
V, E = map(int, input().split())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
A, B, C = map(int, input().split())
graph[A].append((B, C))
graph[B].append((A, C)) # 양방향 그래프
print(prim(graph, 1))많다..
어흥🦁