본문으로 건너뛰기

1197 - 최소 스패닝 트리

info

풀이 키워드​

스포주의

그래프 최소스패닝트리 유니온파인드


풀이 코드​

info
  • 메모리: 50664 KB
  • 시간: 304 ms
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

parent = []

def union(a, b):
    global parent
    
    pa = find(a)
    pb = find(b)
    
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb


def find(x):
    global parent
    
    if parent[x] != x:
        parent[x] = find(parent[x])
    
    return parent[x]


def solution():
    global parent
    
    V, E = map(int, input().split())
    parent = [x for x in range(V+1)] # for union-find
    tree = []
    
    for _ in range(E):
        a, b, weight = list(map(int, input().split()))
        tree.append((weight, a, b))
        
    # Kruskal
    ans = 0
    tree.sort()
    for data in tree:
        weight, a, b = data
        
        if find(a) != find(b):
            ans += weight
            union(a, b)
            
    print(ans)


if __name__ == '__main__':
    solution()

풀이 해설​

문제 이름부터 대놓고 MST 유형임을 홍보하고 있으므로, 크루스칼 알고리즘을 구현하면 된다.

관련 알고리즘 이론은 갓킹독의 강의를 참고하면 쉽게 이해할 수 있다.

크루스칼 알고리즘은 크게 세 가지 step으로 구성된다.

  1. 선택하지 않은 간선 중 가중치 낮은 순으로 간선 선택
  2. 1에서 선택한 간선으로 연결되는 두 정점이 서로 다른 그룹이면, 해당 간선을 최종 선택
  3. 최종 선택한 간선으로 연결되는 두 정점을 같은 그룹으로 union
Union-Find 알고리즘의 설명은
집합의 표현 풀이 내용으로 대체한다.

caution

⚠️TC 입력받을 때 저장 순서 고려하기⚠️

for _ in range(E):
    a, b, weight = list(map(int, input().split()))
    tree.append((weight, a, b))

다음과 같이 입력 받은 순은 정점1 정점2 간선 가중치 순이지만,

크루스칼 알고리즘 구현을 위해 가중치 기준으로 오름차순 정렬하려면 간선 가중치를 0번 인덱스에 두는 것이 더 깔삼하다.

📌크루스칼 알고리즘​
for data in tree:
    weight, a, b = data
    
    if find(a) != find(b):
        ans += weight
        union(a, b)

간선 가중치가 낮은 순으로 순회하며, 해당 간선과 연결된 두 정점이 같은 그룹에 속하는지 find로 체크한다.

만약 같은 그룹이라면 해당 간선을 스패닝 트리에 포함시킬 수 없다. --> 사이클이 형성되기 때문

따라서 서로 다른 그룹일 경우에만 해당 간선의 가중치를 합산하고, 연결된 두 정점은 같은 그룹으로 union 처리한다.

그리고 마지막으로,
문제에서 스패닝 트리 형성이 보장된다고 하였기 때문에, 순회가 종료되면 무조건적으로 정답 값이 도출됨을 알 수 있다.


메모​

  • 그놈의 setrecursionlimit 또 까먹음

채점결과

ㅜㅜ...