[BOJ/PYTHON] 10423. 전기가 부족해

문제 링크: https://www.acmicpc.net/problem/10423

문제 요약

모든 도시에 전기가 공급될 수 있도록 하는 케이블 설치 최소 비용 구하기

케이블이 연결돼있는 도시에는 발전소가 하나만 존재해야

핵심 아이디어

문제를 읽으며 도시가 정점, 도시를 연결하는 케이블이 간선, 케이블 설치 비용이 비용이라는 것을 파악하고, 연결(케이블 설치)을 최소로 한다는 점에서 최소 신장 트리를 떠올리면 된다.

이미 발전소랑 연결된 도시는 연결해줄 필요가 없는데, 처음부터 발전소끼리 연결해 발전소의 최상위 부모를 만들고 시작하면 추가적으로 연결할 필요가 없다. 이후 발전소의 부모가 다를 경우에만 연결해주고, 비용을 더하면 된다.

풀이

#gold2-10423. 전기가 부족해

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split()) # 도시 개수, 설치 가능한 케이블 수, 발전소 개수
power = list(map(int, input().split())) # 발전소 설치된 도시 번호 (전기 공급처)
parent = [i for i in range(n+1)]
edges = []

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

for _ in range(m):
    u, v, w = map(int, input().split()) # u 도시와 v 도시를 연결하는 케이블 설치 시 w의 비용 발생
    edges.append((w, u, v))
    
edges.sort()

for i in range(k-1): # 발전소끼리 연결해줌
    union_parent(power[i], power[i+1], parent)
    
cost_sum = 0
for cost, a, b in edges:
    if find_parent(a, parent) != find_parent(b, parent):
        union_parent(a, b, parent)
        cost_sum += cost

print(cost_sum)

실행 시간

메모리 46764KB, 시간 284ms (python3)