[BOJ/PYTHON] 6497. 전력난

백준 문제 링크: https://www.acmicpc.net/problem/6497

문제 요약

두 집 쌍에 대해 불이 켜질 수 있도록 하면서 최대로 불 꺼야 함 - 절약할 수 있는 최대 액수 구하기

핵심 아이디어

그래프 간선에 가중치가 있는 무방향 그래프가 주어지는데, 길에 불이 켜져야 하고, ‘모든’ 집을 연결하면서도 최소 비용으로 하려면 비효율적인 사이클이 발생하면 안 된다.

사이클이 없는데 최소 비용을 구하는 거라 최소 신장 트리 알고리즘을 사용하면 된다. (그 중에서 크루스칼 알고리즘을 사용함)

부모 노드가 다르면 연결해주는데, x번 집과 y번 집의 부모 노드가 같으면 이미 불이 들어온 것이기에 불을 꺼주면 된다. 불을 꺼주는 케이스에 대한 비용을 더하면 끝

풀이

#gold4-6497. 전력난

import sys
input = sys.stdin.readline

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

while True:
    m, n = map(int, input().split()) # 집의 수, 길의 수
    if m == 0 and n == 0: break
    parent = [i for i in range(m)]
    edges = []
    max_cost = 0 # 절약할 수 있는 최대 비용
    for _ in range(n):
        x, y, z = map(int, input().split()) # x번 y번 집 사이 도로가 있음, 그 거리 z미터
        edges.append((z, x, y)) # 첫 번째를 비용으로: 비용순 정렬 위함
    
    edges.sort()

    for cost, a, b in edges:
        if find_parent(a, parent) != find_parent(b, parent):
            union_parent(a, b, parent)
        else: # 불 꺼도 됨 -> 절약한 비용 발생
            max_cost += cost

    print(max_cost)

실행 시간

메모리 59220KB, 시간 2064ms (python3)