(최소 스패닝 트리)
# 문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
# 입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다.
다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.
이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다.
C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다.
최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
# 출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
먼저 스패닝 트리가 무엇인지 알아보겠습니다!
신나는 나무
스패닝 트리는 다음 조건이 모두 충족되는 경우 트리입니다.
- 모든 노드가 연결되어 있습니다.
- 주기가 존재하지 않습니다.
스패닝 트리의 올바른 예
비신장 트리의 예
연결되지 않은 노드 또는 주기가 있는 경우 트리가 확장되지 않습니다.
'추천 관련글,
최소 스패닝 트리 찾기
- 최소 스패닝 트리 알고리즘: 스패닝 트리 중 최소 비용빌드할 스패닝 트리를 찾는 알고리즘입니다.
최소한의 비용으로 스패닝 트리를 찾는 알고리즘, 크루스칼 알고리즘알아 보자!
크루스칼 알고리즘
- Kruskal 알고리즘은 대표적인 최소 스패닝 트리 알고리즘이다.
1) 모든 간선을 비용 오름차순으로 정렬한다.
2) 비용이 적은 간선을 가져온다.
3) 이 간선이 연결되면 사이클을 발생시키는지 확인한다.
4) 사이클을 발생시키지 않는다면, 이 간선을 신장 트리에 포함시킨다.
~반복~이는 항상 최적의 솔루션을 보장합니다.
1. 비용의 오름차순으로 모든 가장자리를 정렬합니다.
edges = () # 간선
for _ in range(E):
a, b, cost = map(int, sys.stdin.readline().split())
edges.append((cost, a, b))
edges.sort() # 비용순 오름차순 정렬
2. 유리한 이점을 얻으십시오.
- 1단계에서 오름차순으로 정렬해 놓았으니 하나씩 빼주시면 됩니다!
for edge in edges:
cost, a, b = edge # cost 오름차순으로 정렬되어 있음
3. 이 에지가 연결되면 주기가 발생하는지 확인하십시오.
이 에지가 연결될 때 순환을 일으키는지 확인하는 방법,
주어진 모서리의 모든 정점 상위 노드알아보는 것입니다
(각 노드의 부모를 찾아 두 부모가 같으면 그 가장자리가 연결될 때 순환을 일으킬 것입니다!
!
!
)
왜,,주기가 뭐야,,,
연결된 노드가 같은 노드에 연결되면 뒤집어서 서로 만나는 것이 바로 싸이클~!
부모 노드는 각 노드입니다.
가장 작은 연결된 노드수단
이 부모 노드가 동일한 노드를 연결하면 주기가 발생합니다.
위 그림에서 점선으로 표시된 부분입니다.
6-7가장자리가 연결될 때 주기가 발생합니까?
- 7에 연결된 가장 작은 노드는 3이고,
- 6에 연결된 가장 작은 노드는 3입니다.
둘 다 3으로 이어집니다.
다시 말해서, 6-7 에지가 연결되면 주기가 트리거됩니다.
그럴땐 연결하면 안됩니다.
싸이클이 발생하면 스패닝 트리가 아닙니다~!
이제 부모 노드를 먼저 찾아야 합니다.
2-1) 부모 테이블을 생성합니다.
- 인덱스를 노드로 설정하고 값을 부모 노드로 설정합니다.
parent(노드) = 부모노드 - 노드는 1부터 지정되므로 상위 테이블의 크기는 노드 수 + 1입니다.
(인덱스 0을 사용하지 않기 때문입니다!
) - 먼저 자체적으로 초기화합니다.
(노드 1 부모는 1, 노드 2 부모는 2…)
# 부모를 담을 테이블 (parent(노드) = 부모노드)
parent = (0) * (V + 1)
# 부모를 자기 자신으로 초기화
for i in range(1, V+1):
parent(i) = i
2-2) 부모 노드가 동일한지 확인합니다.
이것은 두 번째 for 문으로 이어집니다.
- 비용이 가장 낮은 에지를 선택하고 해당 에지에 연결된 모든 노드에 동일한 부모 노드가 있는지 확인합니다.
(같은 부모는 같은 집합에 속하는 것을 의미합니다.
같은 집합에 속할 필요는 없습니다.
)
for edge in edges:
cost, a, b = edge # cost 오름차순으로 정렬되어 있음
if find_parent(a) !
= find_parent(b): # 같은 집합이 아니면,
- 아래는 부모를 찾는 기능입니다.
함수를 재귀적으로 호출하고 부모 테이블의 값을 즉시 업데이트(경로 압축 기술)하여 시간 복잡도를 개선했습니다.
# 부모 찾는 함수
def find_parent(x):
if parent(x) !
= x:
parent(x) = find_parent(parent(x))
return parent(x)
4. 주기가 발생하지 않으면 스패닝 트리에 에지를 포함합니다.
2 또는 3은 지침을 따릅니다.
result = 0
for edge in edges:
cost, a, b = edge # cost 오름차순으로 정렬되어 있음
if find_parent(a) !
= find_parent(b): # 같은 집합이 아니면,
union_parent(a, b) # 연결
result += cost # 연결된 것 cost 누적- 비용 절감을 위한 변수
result새로 선언했습니다. - 에지가 연결될 때마다 해당 에지의 비용은
result이 값을 최종 결과로 출력합니다. - 실제로 트렁크를 연결하는 부분
union_parent(a, b)이 함수 안에서 발생합니다.
스패닝 트리에 에지를 포함하는 기능
union_parent(a, b) 함수에 무엇이 있는지 봅시다!
def union_parent(a, b):
# 집합(부모 노드) 찾기
a = find_parent(a)
b = find_parent(b)
# 큰 거에서 작은 거로 연결
if a < b:
parent(b) = a
else:
parent(a) = b 연결할 두 노드의 부모를 찾아 연결합니다.
왜?
- 노드를 연결할 때 방향은 큰 노드에서 작은 노드로 향해야 하며 작은 노드가 큰 노드의 부모가 됩니다.
즉, 노드를 연결하려면 큰 노드의 부모 노드를 작은 노드 위에 놓으세요!
! - 그런데,,,,
노드 3과 노드 2가 연결되면,
노드 2가 1에 연결되어 있으므로
노드 3의 부모 노드도 2가 아닌 1이 됩니다. - 따라서 Edge가 연결될 때마다 상위 노드 업데이트그것을해야합니다!
3과 2를 결합할 때 3 -> 2로 끝나는 것이 아니라 2의 부모를 찾아 3과 결합하여 3 -> 1로 변경해야 합니다!
! - 부모노드를 연결하기 때문에 함수는 먼저 부모노드를 찾는다.
find_parent호출하여 찾은
큰 부모 노드를 작은 부모 노드에 연결합니다.
즉, 부모 노드를 함께 연결합니다.
Self와 parent는 당연히 연결되어 있기 때문에 부모 노드만 연결하면 연결이 계속됩니다. - 이와 같이 연결되지 않은 것 중 가장 저렴한 것을 한두 개 추가하여 한 번에 하나씩 연결하여 최소 스패닝 트리를 완성한다.
끝!
전체 코드
import sys
V, E = map(int, input().split()) # 정점의 개수, 간선의 개수
# 부모를 담을 테이블 (parent(노드) = 부모노드)
parent = (0) * (V + 1)
# 부모를 자기 자신으로 초기화
for i in range(1, V+1):
parent(i) = i
# 부모 찾는 함수
def find_parent(x):
if parent(x) !
= x:
parent(x) = find_parent(parent(x))
return parent(x)
# 간선 연결하는 함수(집합 합치기)
def union_parent(a, b):
# 집합(부모 노드) 찾기
a = find_parent(a)
b = find_parent(b)
# 큰 거에서 작은 거로 연결
if a < b:
parent(b) = a
else:
parent(a) = b
edges = () # 간선
for _ in range(E):
a, b, cost = map(int, sys.stdin.readline().split())
edges.append((cost, a, b))
edges.sort() # 비용순 오름차순 정렬
result = 0
for edge in edges:
cost, a, b = edge # cost 오름차순으로 정렬되어 있음
if find_parent(a) !
= find_parent(b): # 같은 집합이 아니면,
union_parent(a, b) # 연결
result += cost # 연결된 것 cost 누적
print(result)