[백준 6497] 전력난 - Python

문제 보기

[사용한 알고리즘]

크루스칼(Kruskal)

 

[문제 접근]

모든 도시는 항상 연결 그래프의 형태이며 최대로 비용을 절약하는 문제이기 때문에 MST(Minimal Spanning Tree) 문제라고 생각하였습니다.

 

[알고리즘]

1. 입력받은 도로의 비용을 기준으로 오름차순 정렬합니다.

2. 비용이 낮은 순서대로 하나씩 선택하여 두 도시를 연결하는 도로를 설치할 수 있는지 확인합니다.

 - 해당 도로 설치로 인해 사이클이 생성될 수 있다면 해당 도로를 설치하지 않습니다.

3. 설치하지 않은 도로의 합을 출력합니다.

 

[코드]

import sys


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


def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


if __name__ == "__main__":
    while True:
        m, n = map(int, sys.stdin.readline().split())
        if m == 0 and n == 0:
            break
        parent = [i for i in range(m)]
        edges = []
        for _ in range(n):
            x, y, z = map(int, sys.stdin.readline().split())
            edges.append((z, x, y))

        # 비용을 기준으로 오름차순 정렬
        edges.sort()
        total = 0
        for i in range(len(edges)):
            z, x, y = edges[i]
            if find_parent(x, parent) != find_parent(y, parent):
                union_parent(x, y, parent)
            else:
                total += z

        print(total)