[백준/Python] 1368. 물대기 - 크루스칼

본 포스팅은 해당 문제를 크루스칼 알고리즘으로 푼 풀이에 대해 정리하였다.
프림 알고리즘으로도 비슷하게 풀 수 있기 때문에 아래 포스팅도 참고 바란다.

📋 참고 포스팅:[백준/Python] 1368. 물대기

---

📄 문제

백준
난이도 : Gold 2
문제 제목 : 물대기

✏️ 풀이 1

import sys
import heapq

# 최소 신장 그래프
input = sys.stdin.readline
n = int(input())
eList = []   # [시작점, 도착점, 비용]
vRoot = [i for i in range(n + 1)]
for i in range(1, n + 1):
    eList.append([0, i, int(input())])
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if i != j:
            eList.append([i + 1, j + 1, tmp[j]])

eList.sort(key=lambda x:x[2])

def find_parent(x):
    if x != vRoot[x]:
        vRoot[x] = find_parent(vRoot[x])
    return vRoot[x]

result = 0
for u, v, w in eList:
    u_p = find_parent(u)
    v_p = find_parent(v)
    if u_p != v_p:
        if u_p > v_p:
            vRoot[u_p] = v_p
        else:
            vRoot[v_p] = u_p
        result += w
        
print(result)

✅ 풀이 한줄 설명:
최소 신장 트리를 구하는 크루스칼 알고리즘을 적용한 풀이이다.
직접 논의 위치에 우물을 팔 수도 있어서 초기에 간선 리스트에 각 논에 대한 [시작점, 시작점, 비용]을 추가해야 한다.
만약 최소 신장 트리 알고리즘을 잘 모른다면 먼저 공부해보기를 추천한다. (위 풀이에서는 크루스칼 알고리즘과 프림 알고리즘 중 크루스칼 알고리즘을 사용하였다. 그러나 둘 다 공부해오기를 추천한다.)

✅ 풀이 자세한 설명:

1. 간선 리스트 만들기
2. 크루스칼 알고리즘 수행하기

🍎 1. 간선 리스트 만들기
직접 논의 위치에 우물을 팔 수도 있어서, 먼저 간선 리스트에 각 논에 대한 [0, 논의 인덱스, 비용]들을 추가해야 한다.

조금 더 쉽게 이해하기 위해, 가상의 정점(논) 0이 있다고 생각하는 것이 좋다.

위와 같은 그래프가 주어졌다면, 아래와 같이 가상의 논 0을 추가해 생각해주는 것이다.

즉 직접 논의 위치에 우물을 파는 것을, 위 사진과 같이 가상의 논 0에서 각 논으로의 간선으로 보면 된다. 그러면 일반적인 최소 신장 트리 구하는 문제로 생각할 수 있다.

🍎 2. 크루스칼 알고리즘 수행하기
최소 신장 트리의 크루스칼 알고리즘을 수행한다.
간선 리스트를 비용 순으로 정렬하여 비용이 적은 순서대로 꺼내 반복문을 수행한다.
만약 꺼낸 두 논(정점)이 이미 이어져 있으면 아무것도 하지 않고,
이어져 있지 않다면 이어준다.
이어준 경우(물을 대준 경우), 비용을 result에 추가한다.

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '1368. 물대기'
GitHub - [27강] 최소 신장 트리/연습문제 '1368. 물대기'