[백준]1197번 - 최소 신장 트리, Kruskal, Prim

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

크루스칼 알고리즘

import sys

# 특정한 노드의 부모가 누구인지 찾는 함수
def find(target):
    if target == parent[target]:
        return target

    parent[target] = find(parent[target])
    return parent[target]

# 부모 노드를 합치는 함수
def union(a, b):
    a = find(a)
    b = find(b)

    # 더 작은 값쪽으로 부모노드를 합침
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = list(map(int, (input().split())))
costs = []
visited = [1]
answer = 0
for _ in range(e):
    costs.append(list(map(int, sys.stdin.readline().split())))
    
# 크루스칼 알고리즘을 위해 가중치를 오름차순으로 정렬
costs.sort(key=lambda x: x[2])

# parent -> 부모노드가 누구인지 적혀있는 리스트
parent = [0]
for p in range(1, v+1):
    parent.append(p)

for cost in costs:
    s, e, c = cost
    # 두 노드가 사이클을 형성하지 않을 경우에만 합침
    if find(s) != find(e):
        answer += c
        union(s, e)
print(answer)

이번에도 역시 크루스칼 알고리즘과 유니온 파인드 알고리즘을 활용하였다. 저번에 풀이한 프로그래머스 문제과 같은 유형이기에 해당 알고리즘을 확실하게 이해하기 위해 풀어보았다.

문제 해결 Point

저번 문제와 같은 유형이니 간단한 설명으로 넘어가겠다.

1. 특정한 노드의 부모노드를 찾는 함수인 find, 부모 노드를 합치는 함수인 union을 정의한다.
2. 각 정점의 부모노드가 누구인지 적혀있는 parent 리스트에 자신의 정점번호로 초기화를 한다.
3. costs 리스트를 순회하면서 사이클을 형성하지 않는 경우에만 가중치를 더하고, union을 해줌으로써 정답을 도출할 수 있다.

 

프림 알고리즘

import sys
import heapq

v, e = list(map(int, (input().split())))
costs = [[] for _ in range(v+1)]

# 각 정점의 가중치와 인접정보를 넣어주는 반복문
for _ in range(e):
    s, e, c = map(int, sys.stdin.readline().split())
    costs[s].append([c, e])
    costs[e].append([c, s])

# 방문 체크를 위한 리스트
visited = [False] * (v+1)
answer = 0
cnt = 0

# 최소 힙을 통해서 우선순위큐를 구현함, 가중치 순으로 정렬되게 하여 가장 낮은 cost를 고르도록 한다.
heap = []
heapq.heappush(heap, (0, 1)) # (cost, start) 시작지점은 1 노드, cost도 0
while cnt < v: # 간선의 갯수가 v-1이 되면 종료
    c, s = heapq.heappop(heap)
    if visited[s]: # 이미 방문한 노드라면 건너뜀
        continue
    visited[s] = True
    answer += c
    cnt += 1
    for cost in costs[s]:
        # 방금 방문한 정점의 간선정보를 넣어줌
        heapq.heappush(heap, cost)
print(answer)

문제 해결 Point

1. 각 정점의 가중치와 인접정보를 넣어주어 해당 정점에 어떤 정점이 연결되어 있는 지를 보여준다.
2. 방문 체크를 위한 리스트를 활용한다.
3. 최소 힙을 사용해서 우선순위 큐를 구현하고, 이를 통해 가중치가 가장 낮은 간선부터 이용되게 한다.
4. 연결된 간선의 수가 v-1이 될 때 까지 반복을 진행한다.
   1. 우선순위 큐에서 가장 가중치가 낮은 정보를 꺼낸다.
   2. 방문을 하지 않은 노드일 경우 방문처리를 수행하고, 가중치를 더한다.
   3. 방금 방문한 정점에 대한 간선 정보를 우선순위큐에 넣어준다.

 

자세한 설명은 아래의 두 링크에서 확인하실 수 있습니다. (같은 유형 다른 문제)

https://leffept.tistory.com/386

[프로그래머스]섬 연결하기 - 그리디, 최소 신장 트리, Prim

https://leffept.tistory.com/383

[프로그래머스]섬 연결하기 - 그리디, 최소 신장 트리, Kruskal