[백준 1414] 크루스칼 알고리즘(Kruskal , 최소신장트리) - 파이썬(Python)

불우이웃돕기

문제

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

예제 입력 1

3
abc
def
ghi

예제 출력 1

40

---

최소 신장 트리 

최소 신장 트리는 모든 노드가 연결되도록 간선을 그은 트리의 가중치의 합이 가장 작은 것을 말합니다. 가중치의 값이 최소가 돼야되기 때문에 사이클은 없어야 합니다

---

크루스칼 알고리즘

 크루스칼 알고리즘은 최소 신장 부분 트리를 찾는 알고리즘으로 가중치가 가장 낮은 엣지를 순서대로 고르지만, 사이클이 안생기도록 고르는 알고리즘입니다.

변의 개수를 E, 꼭짓점의 개수 V라고 하면 이 알고리즘은O(E\log V)의 시간복잡도를 가집니다.

 

1. 엣지리스트 초기화 하기

엣지들을 가중치가 낮은것 순서대로 뽑을 것이므로 리스트에다가 넣고, 나중에 정렬해줍니다.

2. 유니온 파인드 알고리즘 적용시키기

유니온 파인드는 쉽게 말해서 집합을 구현하는 알고리즘입니다. 아래 코드를 보시면 겉핥기로 이해되실 것입니다 (크루스칼 포스트이므로 상세하게 설명은 안하겠습니다.)

n, m = map(int, sys.stdin.readline().rstrip().split())

parent = [i for i in range(n+1)]

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x]) # get_parent 거슬러 올라가면서 parent[x] 값도 갱신
    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if a < b: # 작은 쪽이 부모가 된다. (한 집합 관계라서 부모가 따로 있는 건 아님)
        parent[b] = a
    else:
        parent[a] = b        

def same_parent(a, b):
    return get_parent(a) == get_parent(b)

이 알고리즘 형식을 더 간단하게 해서 구현할 것 입니다.

---

 

엣지들이 있을때 가중치가 가장 낮은 엣지를 우선적으로 선택해서 차례대로 연결합니다.

만약에 연결하면 사이클이 생기면, 건너뛰고 다음 엣지부터 검토합니다.

사이클이 생기는 지 여부는 유니온 파인드 알고리즘을 통해 판별할 수 있습니다.

---

 

예를 들면 가중치가 9인 빨간색 엣지의 양끝 노드를 보면 B,D인데 둘다 같은 유니온(집합)에 속해있기 때문에 사이클이 생기므로 건너뛰고 다음 엣지를 살펴봅니다.

---

N이 노드의 갯수라고 할때, 탐색을 전부완료하면 N-1개의 엣지가 있어야되고, 모든 노드들이 한 유니온으로 연결되어있어야합니다.

---

파이썬 코드

문제를 보면 알겠지만 모든 컴퓨터(노드)가 최소 길이의 엣지(랜선)으로 다 연결돼있다는것이 최소 신장 트리라는 것을 깨달을 수 있습니다.

 

a,z등등을 숫자로 바꾸는건 문자의 아스키코드값을 구하는 파이썬 함수인 ord를 쓰면 됩니다.

 

주의할 점은 길이가 0이면 가중치가 0인 엣지가 아니라 존재하지 않는 엣지인 것입니다.

 

그것을 유의해서 사이클 없이 n-1개의 엣지가 연결되도록 코드를 짜고, n-1개 까지 못고르면 다 연결하는게 불가능하므로 -1을 출력합니다.

 

엣지들을 다 연결해서 총 이용한 엣지 가중치를 구하고, 기존 모든 엣지합에서 빼면, 기부하는 랜선의 갯수가 됩니다.

import sys
from queue import PriorityQueue
input = sys.stdin.readline


n = int(input())
edges = [[] for _ in range(n)]
parant = [0] * n
for i in range(n):
    parant[i] = i
total = 0
heap = PriorityQueue()
for i in range(n):
    li = list(input().strip())
    for j in range(n):
        ask = ord(li[j])
        if ord('a')<=ask<=ord('z'):
            ask = ask - ord('a') + 1
        elif ord('A')<=ask<=ord('z'):
            ask = ask - ord('A') + 27
        else:
            ask = int(li[j])
        total += ask
        if ask!=0 and i!=j:
            heap.put((ask,i,j))

def find(a):
    if a == parant[a]:
        return a
    else:
        parant[a] = find(parant[a])
        return parant[a]

def union(a,b):
    a = find(a)
    b = find(b)
    if a!=b:
        if a<b:
            parant[b] = a
        else:
            parant[a] = b



cnt = 0
use = 0
while heap.qsize() != 0:
    if cnt >= n-1:
        break
    w,a,b = heap.get()
    if find(a) == find(b):
        continue
    cnt += 1
    use += w
    union(a, b)

if cnt == n-1:
    print(total - use)
else:
    print(-1)