알고리즘 유형 : MST
풀이 참고 없이 스스로 풀었나요? : 학습
https://www.acmicpc.net/problem/1197
SOLVE 1
Kruskal 풀이
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
# 유니온 파인드
def find(v):
if MST[v] < 0:
return v
MST[v] = find(MST[v])
return MST[v]
# 유니온 성공 여부를 리턴한다.
# 유니온이 성공했을때만(True) 이 때 사용한
# 간선의 가중치를 ans에 누적하여 더해준다.
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
if MST[root_a] < MST[root_b]:
MST[root_b] = root_a
elif MST[root_a] > MST[root_b]:
MST[root_a] = root_b
else:
MST[root_a] = root_b
MST[root_b] -= 1
return True
V, E = map(int, input().split())
graph = []
MST = [-1]*(V+1)
for _ in range(E):
A, B, C = map(int, input().split())
graph.append((C, A, B))
# 가중치 기준 오름차순 정렬(Tim sort, 퀵 정렬 베이스)
graph.sort()
res = 0
for cost, a, b in graph:
# 유니온 함수에, 사이클 존재 여부 검사와
# 두 노드 한 집합에 넣기 기능이 둘 다 들어있음
# 만약 union이 성공했다는 것은 해당 간선을 선택
# 했을 때 사이클이 없다는 뜻이므로, 그 간선을 선택
# 한 후, 가중치를 res에 누적해준다.
# E개의 간선에 대해 union 안에서 find 함수가 log(E) 이므로
# O(ElogE)
if union(a, b):
res += cost
print(res)SOLVE 2
Prim 풀이
import sys
input = sys.stdin.readline
INF = sys.maxsize
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))
visited = [False]*(V+1) # 노드 탐색 여부
# 부분 MST인 집합 T에 대해, T에 속한 노드로부터
# idx 노드까지 도달하는 최소 가중치
dist = [INF]*(V+1)
# V번 도는 for문의 수행 내용은 T와 그외 노드에 대한 최소 가중치
# 간선을 찾고, T에서 그 간선의 끝 노드로 탐색을 하고, 그 노드의
# 인접 노드들의 dist값을 갱신해주는 것임. 따라서, 최초에는
# T는 공집합이므로, 임의의 노드(여기선 1로 정하자)로 뻗어나가야
# 하므로 우선 1의 dist 값을 0으로 초기화해둔 것이다.
dist[1] = 0
# V번 수행하면서 V개의 노드를 모두 MST 조건에 맞게 탐색한다.
for _ in range(V):
min_dist = INF
next_node = None
# 현재 T에서, T에 있지 않은 그래프 상 노드 중에 최소 가중치
# 로 도달할 수 있는 노드를 찾음
for i in range(1, V+1):
if visited[i] == False and dist[i] < min_dist:
min_dist = dist[i]
next_node = i
# 도달 노드를 찾았으면, 방문 표시를 하고 그 노드의
# 인접 노드들의 dist 값을 갱신해줌. 이 때, 도달 노드의
# dist 값은 건들 필요없음. 이전 순회 단계에서, 다음과 같은
# 인접 노드 갱신 프로세스가 수행되었었기에 이미 dist 값이
# 갱신돼있는 상태이기 때문
visited[next_node] = True
for adj_node, cost in graph[next_node]:
if visited[adj_node] == False:
dist[adj_node] = min(dist[adj_node], cost)
print(sum(dist[1:]))SOLVE 3
Prim(우선순위 큐 활용) 풀이
import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize
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((C, A, B))
graph[B].append((C, B, A))
def prim(start_node):
visited = [False]*(V+1)
visited[start_node] = True
MST = [] # MST path
candidate = graph[start_node] # T와 T에 없는 노드를 잇는 간선이 들어있는 최소힙
total_weight = 0
heapq.heapify(candidate)
while candidate:
w, x, y = heapq.heappop(candidate) # 최소 가중치 간선 뽑기
# 아직 T에 안 넣은 노드라면 방문 표시하고 path 리스트와
# total_weight 갱신해주기
# 이 후 그 노드와 인접 노드를 잇는 간선을 힙에 넣어준다.
# 만약에 인접 노드와 연결된 간선이 힙에 여러 개 들어있다면,
# 최소 힙 구조에 의해 그 간선들 중에서 최소 가중치 간선이
# 먼저 뽑혀 처리될 것이고, 나머지 간선은 나중에 뽑혔을 때
# visited 조건문에 걸려 자연스럽게 탈락된다. 그러므로
# 최소 가중치 간선을 뽑는 그리디한 로직은 무사히 수행된다.
if visited[y] == False:
visited[y] = True
MST.append((x, y))
total_weight += w
for edge in graph[y]:
if visited[edge[2]] == False:
heapq.heappush(candidate, edge)
return MST, total_weight
path_MST, total_weight = prim(1)
print(total_weight) # 이 문제는 MST 가중치 합만 필요하니 이 것만 출력해주자.SOLVE 1) 풀이 요약 (크루스칼 풀이)
-
크루스칼 풀이는 그래프의 모든 간선에 대해, 가중치가 가장 적은 것부터 하나씩 골라서 유니온 파인드로 최소 비용 신장 트리를 만들어가는 풀이이다.
그리디한 알고리즘인데, 이렇게 구한 해가 일반해로 보장이 된다는 것은 귀류법으로 증명되어있다.
-
우선 모든 간선 정보를 가중치 기준 오름차순 정렬해준다.
이 후 가장 적은 가중치의 간선부터 하나하나씩 골라서 유니온해준다. 유니온 파인드 로직에 따라, 선택된 간선의 양 끝 노드가 이미 같은 집합 내에 있거나, 사이클을 형성하는 경우가 배제된다.
즉, 모든 간선을 순회하며 유니온 파인드를 실행하고나면, 최소 비용으로 모든 노드를 연결했기에 최소 비용 신장 트리가 완성된다.
- 간선을 가중치 기준 오름차순으로 정렬할 때, 퀵정렬 기준 O(ElogE)이다. 이 후 유니온 파인드에서 실행하는 find 함수는 최적화 시 시간복잡도가 상수에 가까우므로, 크루스칼의 시간복잡도는 곧 O(ElogE)가 된다.
SOLVE 2 풀이 요약 (프림 풀이)
-
프림 풀이는 모든 노드를 순회하면서 MST를 만든다. (참고로 이 풀이는 pypy3로 제출해야 통과)
집합 T를 두고, 여기에 노드를 하나씩 집어넣을건데, T와 T에 속하지 않은 노드들에 대해, T에서 가장 최소 가중치로 도달할 수 있는 노드를 T에 집어넣는 동작을 반복한다.
마찬가지로 그리디하게 동작하고, 이 것이 일반해를 보장함은 귀류법으로 이미 증명된 바이다.
-
우선 visited와 dist 배열을 만든다. 길이는 V+1이고, 그 값은 각각 False와 INF이다.
visited[idx]는 idx 노드를 T에 넣었는지 여부를 나타내고, dist[idx]는 T의 모든 노드 중에서 idx 노드로 도달하는 간선의 가중치 중 최솟값을 의미한다.
V개의 노드를 모두 T에 집어넣어 MST를 만들것임으로, 전체 for문은 V번 반복한다.
그 for문 내부에서 동작하는 내용은 두 가지가 있다.
1) T에 속하지 않은 노드 중에, T에서 최소 가중치로 도달할 수 있는 노드를 찾는다.
2) 그 노드에 방문 표시를 하고(visited, T에 넣어짐을 의미), 그 노드의 인접 노드의 dist 값을 갱신해준다. (기존의 dist값과, 본인으로부터 출발하여 인접 노드로 가는 cost 중 최솟값으로 갱신해줌)
-
for문을 끝낸 후 dist[1:]의 sum 값을 출력해준다. dist의 각 값은, 그 노드 바로 직전의 어느 노드에서 그 노드까지의 cost 중 최소를 의미한다. 따라서, 간선 하나의 가중치 값에 해당한다.
그리고 그 간선들 자체가 MST를 구성하므로, 모든 값을 더해주면 곧 MST를 구성하는 모든 간선의 가중치를 합한 것과 같다.
참고로 이 알고리즘은 이중 for문이고 각 for가 V번 반복하므로 시간복잡도는 O(V^2)이다.
SOLVE 3 풀이 요약 (프림(우선순위 큐 활용) 풀이)
-
개선된 프림 알고리즘으로 푼다.
우선순위 큐, 그 중에서 최소 힙을 활용한다.
이 풀이에서는 candidate(최소 힙)에 간선이 없을 때까지 while문을 반복한다.
candidate는 T에서 T에 속하지 않는 노드로 도달하는 간선들이 담겨 있는 최소 힙이다.
while 내부에서는 다음을 수행한다.
1) candidate에서 간선 하나를 뽑는다. (T에 속하지 않는 노드로 도달하는 간선 중 최소 가중치)
2) 간선의 끝 노드가 아직 미방문 상태(T에 안속함)라면, 방문 표시를 하고 total_weight에 가중치를 더해준다.
3) 이 노드의 인접 노드들에 대해, 미방문 상태라면 해당 간선 정보를 힙에 넣어준다.
-
while문이 끝나고 나면 total_weight를 리턴 및 출력해주면 된다.
이 때 시간복잡도는, 우선 프림 알고리즘은 모든 노드가 T에 들어갈 때까지 수행하므로 while문은 V번 내외로 실행되고, 그 만큼 힙에서 간선을 뽑으므로 VlogV, 인접 노드를 순회하면서 조건에 따라 힙에 넣는 것은 ElogV, 즉 O(VlogV + ElogV) = O(ElogV)이다. (트리를 구성하므로 E는 최소 V-1이여야함. 즉 E는 V-1 이상의 값이므로, 빅오 표기법을 ElogV로 간략히 표현한다.
배운 점, 어려웠던 점
- 최소 신장 트리의 개념과, 그 것을 만드는 방법인 크루스칼과 프림에 대해 배웠다. 이해하기가 생각보다 쉽지 않았기에 시간을 제법 들였다...
