[BOJ/백준] 1197 최소 스패닝 트리

import sys
input = sys.stdin.readline
 
 
 
 
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][B] = C
    graph[B][A] = C
INF = float('inf')
visited = [False]*(V+1)
distance = [INF]*(V+1)
distance[1] = 0
 
node_list = [(1,0)]
cnt = 1
result = 0
while cnt <V:
    node, dis = node_list.pop()
    current_min_dis = INF
    current_min_node = -1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] =  graph[node][next_node]
 
    for ind in range(1,V+1):
        if current_min_dis > distance[ind] and not visited[ind]:
            current_min_node = ind
            current_min_dis = distance[ind]
    node_list.append((current_min_node,current_min_dis))
    result += current_min_dis
    cnt += 1
 
print(result)

첫 풀이는 다익스트라랑 비슷한 프림 알고리즘을 이용한 풀이였다. 하지만 해당 풀이는 실행시간이 오래걸려서 또 다른 방식으로 풀었다.

 

 

import sys
import heapq
 
input = sys.stdin.readline
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][B] = C
    graph[B][A] = C
INF = float('inf')
distance = [INF]*(V+1)
visited = [False]*(V+1)
node_list = []
distance[1] = 0
heapq.heappush(node_list,(0,1))
result = 0
while node_list:
    key,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += key
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            heapq.heappush(node_list,(graph[node][next_node],next_node))
            distance[node] = graph[node][next_node]
print(result)

두번째는 프림 알고리즘이지만, heapq를 활용한 풀이였다. 위의 방식과 똑같지만, distance가 갱신될때에만을 판단하고, 그때 node_list에 추가하는 방식이었다.

 

 

import sys
 
input = sys.stdin.readline
def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x
 
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]
 
 
 
 
V,E = map(int,input().split())
 
grpah = sorted([list(map(int,input().split())) for _ in range(E)],key=lambda x : x[2],reverse=True)
 
make_set = [i for i in range(V+1)]
 
cnt = 1 
result = 0
 
while cnt <V:
    p1,p2,weight = grpah.pop()
    if find_parent(p1) != find_parent(p2):
        union(p1,p2)
        result += weight
        cnt += 1
 
print(result)

크루스칼 알고리즘으로 푼 방식이다. 크루스칼 알고리즘이 편한사람들은 금방 푼다고하는데, 크루스칼 알고리즘에 익숙하지 못해서 시간이 오래걸렸다.

 

많이 실패했던것은 make_set에 저장된 parent_node로 비교를 했을때 틀렸다. find_parent 이후에, 루트노드가 바뀐 경우 make_set에 저장된 모든 parent들이 root_node로 갱신되는것이 아니기 때문에, 문제가 생겼었다.

 

 

프림 알고리즘과 크루스칼 알고리즘은 자주 쓰이므로 좀 더 익숙해져야겠다.