BOJ 10423: 전기가 부족해 [Python 3]

멘토님께서 추천해주신 골드 난이도를 자랑하는 '전기가 부족해'라는 문제이다.

이 문제의 특징은, 기존의 문제는 각 지점까지의 거리가 '1' 이나 특정 숫자로 정해져 있어서, 단순히 지점까지의 거리를 일괄적으로 계산하기 유리했는데, 이번 각 지점사이의 비용이 모두 상이하기에, 기존의 문제 해결 방법으로 풀 수 없었다.

 

그래서 이번에 사용한 알고리즘은 

Kruskal Algorithm이다. (크루스칼 알고리즘)

 

크루스칼 알고리즘은 그래프 내에 있는 모든 점들을 제일 적은 비용으로 연결할 수 있는 방법이다.

 

'신장 트리' 중 제일 비용의 합이 적은 '최소 신장 트리' (Minimum Spanning Tree) 를 구하는 과정이다.

(신장 트리란 '사이클'을 형성 하지 않는 선에서, 모든 노드가 적어도 하나의 간선으로는 연결되어 있는 트리이다.)

 

크루스칼 알고리즘은 , 'Greedy' 하게 간선들을 돌아다닌다.

간선들의 비용을 오름차순으로 정렬하고, 사이클이 형성 하지 않는 선에서 간선들을 선택하는 알고리즘이다.

import sys
input=sys.stdin.readline
def find_parent(parent,x):
    if parent[x]!=x:
        return find_parent(parent,parent[x])
    return x
def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
n,m,k=map(int,input().split())
gen=list(map(int,input().split()))
lines=[list(map(int,input().split())) for _ in range(m)]
parent=[0]*(n+1)
for i in range(1,n+1):
    if i in gen:
        continue
    parent[i]=i
result=0
lines.sort(key=lambda x: x[2])
for i in lines:
    a,b,val=i
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=val
print(result)

사이클을 판단 하기 위해서, Union&Find라는 알고리즘을 사용했다.

Find부터 알아보자.

발전소를 제외한 모든 노드들은 처음에 자기 자신을 parent로 가르키고 있다.

(발전소는 모두 0을 가르킨다.)

 

만약 어떤 노드를 확인했을 때, 해당 좌표가 자기 자신을 가르키고 있지 않다면, 해당 노드가 아닌 다른 노드가 자신의 parent임을 의미하므로, 자기 자신을 가르키는 parent가 나올때까지 찾는다. (진짜 제일 높은 parent를 조의 '조장'인 것 처럼 찾는다.)

 

Union은 만약 두 노드가 서로 있을 때, 두 노드의 parent를 비교하면서, 두 노드의 parent가 서로 다르다면, parent 중 더 parent의 값이 더 낮은 사람을 따르도록 한다.

만약 두 노드의 parent가 서로 같다면, 결국 한 묶음 사이에 있다는 뜻으로, 이 둘을 이으면 사이클이 생기기 때문에, union을 진행하지 않는다.

 

알고리즘.. 어렵다!