[백준/약점체크] 1197번: 최소 스패닝 트리

[문제]

 

[정답]

최소 신장 트리는 크루스칼 알고리즘이나 프림 알고리즘으로 찾을 수 있다.

크루스칼 알고리즘과 이를 위한 합집합 찾기 알고리즘 그리고 프림 알고리즘에 대한 글을 별도로 작성했으니 참고하면 되겠다.

 

크루스칼 알고리즘

import sys
input = sys.stdin.readline
 
V, E = map(int, input().split())
Vroot = [i for i in range(V+1)]
Elist = []
for _ in range(E):
    Elist.append(list(map(int, input().split())))
 
Elist.sort(key=lambda x: x[2])
 
 
def find(x):
    if x != Vroot[x]:
        Vroot[x] = find(Vroot[x])
    return Vroot[x]
 
 
answer = 0
for s, e, w in Elist:
    sRoot = find(s)
    eRoot = find(e)
    if sRoot != eRoot:
        if sRoot > eRoot:
            Vroot[sRoot] = eRoot
        else:
            Vroot[eRoot] = sRoot
        answer += w
        
print(answer)

- 간선 가중치를 기준으로 리스트를 sort 한다

- find 연산을 정의한다 (그 원소가 속한 트리의 root를 반환한다)

- sort 된 리스트에서 요소를 하나씩 꺼내며 for 문

     - 연결된 두 노드의 root값을 각각 찾는다

     - 두 노드의 root가 같지 않으면 다른 그래프라는 의미이므로 연결한다

     - 이때, 둘 중에 더 작은 쪽을 root로 삼는다

     - 마지막으로 가중치를 모두 더해준다

 

 

프림 알고리즘

import sys
import heapq
input = sys.stdin.readline
 
V, E = map(int, input().split())
visited = [False]*(V+1)
Elist = [[] for _ in range(V+1)]
heap = [[0, 1]]
for _ in range(E):
    s, e, w = map(int, input().split())
    Elist[s].append([w, e])
    Elist[e].append([w, s])
 
answer = 0
cnt = 0
while heap:
    if cnt == V:
        break
    w, s = heapq.heappop(heap)
    if not visited[s]:
        visited[s] = True
        answer += w
        cnt += 1
        for i in Elist[s]:
            heapq.heappush(heap, i)
 
print(answer)

- Elist 구성하는 부분 유의

- 우선순위 큐를 [[0, 1]]로 초기화 (가중치 0, 시작노드 1)

- 첫번째 while iteration : 힙에서 가중치 0, 시작노드 1을 꺼낸다 -> visited 에서 노드1을 방문했음을 표시한다 -> 노드1과 연결된 노드들과 간선 가중치들을 heap 에 넣는다

- 그 다음 iter : 노드1과 연결된 노드들 중에서 가중치가 가장 작은 것을 꺼낸다 -> visited에서 해당 노드를 방문했음을 표시한다 -> 그 노드와 연결된 노드들과 간선 가중치들을 heap에 넣는다

- 그 다음 iter : heap에 들어 있는 노드들 중에서 가중치가 가장 작은 인접 간선을 꺼낸다 -> ... 반복

- 가중치를 더한 횟수와 노드의 갯수가 일치하면 종료한다