[Python] 백준 6497 전력난 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://www.acmicpc.net/problem/6497

6497번: 전력난

 

 

문제 해결 포인트

- 크루스칼 (최소 스패닝 트리) 알고리즘

- find 함수 : 부모 노드(어느 집합에 속하는지) 확인

- union 함수 : 정점 a, b를 같은 집합에 속하도록 parent 업데이트

 

- 여러 테스트케이스 있으므로 n, m이 0, 0 일때 종료 조건으로 무한 반복

- edges : 간선을 비용 기준 오름차순으로 저장

- parent : 각 정점의 부모, 즉 집합을 저장

 

- 정렬된 edges를 차례로 방문하며 사이클 발생하지 않으면 연결

 

작성 코드

import sys
input = sys.stdin.readline


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

def union(a, b):
    a = find(a)
    b = find(b)
    minP, maxP = min(a, b), max(a, b)
    parent[maxP] = minP


while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break
    edges = []
    parent = [i for i in range(m)]
    result = 0

    for _ in range(n):
        x, y, z = map(int, input().split())
        edges.append((z, x, y))
        result += z

    edges.sort()

    for w, x, y in edges:
        if find(x) != find(y):
            union(x, y)
            result -= w

    print(result)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚