310. 전기가 부족해
1) 어떤 전략(알고리즘)으로 해결?
-
최소 스패닝 트리 : 크루스칼
-
최소 신장 트리 :
- 최소 신장 트리는 모든 노드가 연결되도록 간선을 그은 트리의 가중치의 합이 가장 작은 것을 말합니다.
- 가중치의 값이 최소가 돼야되기 때문에 사이클은 없어야 합니다.
=> 사이클이 형성되지 않는 간선끼리 이어서 최소 비용 트리
2) 코딩 설명
<내 풀이>
import sys
def find(x) :
if x!=parent[x] :
parent[x] = find(parent[x])
return parent[x]
def union(a,b) :
a = find(parent[a])
b = find(parent[b])
if a<=b :
parent[b] = a
else :
parent[a] = b
answer = 0
# 모든 도시에 전기를 공급할 수 있도록 케이블을 설치하는 데 드는 최소비용
arr = []
# 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K
N,M,K = map(int,sys.stdin.readline().rstrip().split())
parent = [i for i in range(N+1)]
# 발전소인 도시의 부모를 통일
elec_list = list(map(int,sys.stdin.readline().rstrip().split()))
for elec in elec_list :
parent[elec] = 0
for i in range(M) :
# u 도시에서 v 도시로 가는 케이블
u,v,cost = map(int,sys.stdin.readline().rstrip().split())
arr.append((u,v,cost))
# 케이블 비용 기준으로 오름차순
# 케이블 설치 비용을 최소로 사용하여 모든 도시에 전기가 공급할 수 있도록 해결해야 한다.
cable_list = sorted(arr, key = lambda x : x[2])
for cable in cable_list :
u,v,cost = cable
if find(u)!=find(v) :
union(u,v)
answer+=cost
print(answer)
<반성 점>
- 크루스칼 알고리즘을 정말 까먹고 있었다 !
- 크루스칼 정리 블로그를 통해 내용 다시 복습 !
- 크루스칼, 최소 스패닝
크루스칼 알고리즘
-
최소 스패닝 트리 : 크루스칼
-
최소 신장 트리 :
- 최소 신장 트리는 모든 노드가 연결되도록 간선을 그은 트리의 가중치의 합이 가장 작은 것을 말합니다.
- 가중치의 값이 최소가 돼야되기 때문에 사이클은 없어야 합니다.
- 크루스칼 알고리즘에서 간선이 사이클을 만드는지는 union연산과 find연산을 사용합니다.
- 이는 Union-Find 알고리즘이라고도 부르고 서로소 집합 알고리즘이라고도 합니다.
- 이 알고리즘은 여러 노드가 존재할 때 두 개의 노드를 선택해 루트를 확인하고 현재 서로 같은 그래프에 속하는지 판별합니다.
- 상호 배타적 집합들은 1차원 리스트로 표현하며 루트의 리스트 원소에는 루트 자신이 저장되고 루트가 아닌 노드의 원소에는 부모 노드가 저장됩니다.
- union은 두 개의 집합을 하나의 집합으로 합치는 연산입니다.
- find는 find연산을 수행하면서 루트까지 올라가는 경로 상의 각 노드의 부모 노드를 루트로 갱신합니다.
- 이를 경로 압축이라 하는데 이를 실행하면서 수행 시간을 단축시켜 줄 수 있습니다.
<배운 점>
- 두번째 요소 기준으로 정렬
arr = sorted(arr,key=lambda x:x[2])