[전기가 부족해/G3/Python3]

10423번 전기가 부족해 G3

 

문제
세계에서 GDP가 가장 높은 서강 나라는 소프트웨어와 하드웨어 기술이 모두 최고라서 IT강국이라 불리고, 2015년부터 세상에서 가장 살기 좋은 나라 1등으로 꼽히고 있다. 살기 좋은 나라 1등으로 꼽힌 이후 외국인 방문객들이 많아졌고, 그에 따라 전기 소비율이 증가하여 전기가 많이 부족한 상황이 되었다. 따라서 서강 나라의 대통령은 최근 개발이 완료된 YNY발전소 프로젝트를 진행하기로 하였다. 발전소를 만들 때 중요한 것은 발전소 건물과 도시로 전기를 공급해 줄 케이블이다. 발전소는 이미 특정 도시에 건설되어 있고, 따라서 추가적으로 드는 비용은 케이블을 설치할 때 드는 비용이 전부이다. 이 프로젝트의 문제는 케이블을 설치할 때 드는 비용이 굉장히 크므로 이를 최소화해서 설치하여 모든 도시에 전기를 공급하는 것이다. 여러분은 N개의 도시가 있고 M개의 두 도시를 연결하는 케이블의 정보와 K개의 YNY발전소가 설치된 도시가 주어지면 케이블 설치 비용을 최소로 사용하여 모든 도시에 전기가 공급할 수 있도록 해결해야 한다. 중요한 점은 어느 한 도시가 두 개의 발전소에서 전기를 공급받으면 낭비가 되므로 케이블이 연결되어 있는 도시에는 발전소가 반드시 하나만 존재해야 한다. 발전소가 설치된 도시는 전기가 공급될 수 있기 때문에 상관없다.

입력
첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N) 개가 주어진다.
둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다.
셋째 줄부터 M개의 두 도시를 연결하는 케이블의 정보가 u, v, w로 주어진다. 이는 u도시와 v도시를 연결하는 케이블을 설치할 때 w의 비용이 드는 것을 의미한다. w는 10,000보다 작거나 같은 양의 정수이다.

출력
모든 도시에 전기를 공급할 수 있도록 케이블을 설치하는 데 드는 최소비용을 출력한다.

 

그래프 이론, 최소 스패닝 트리

 

MST 알고리즘인 프림 알고리즘과 크루스칼 알고리즘을 사용한 2가지 풀이 방법을 준비했다.

 

 

프림 알고리즘은 특정 정점에서 시작해서 연결 가능한 간선 중 최소의 가중치를 가지는 간선을 지속적으로 선택해서 최종적인 MST를 구하는 알고리즘이다.

다익스트라와 유사한 방식이지만, 최소 신장 트리를 찾는 프림 알고리즘과 달리 최단 경로를 찾는다는 점에서 목적이 조금 다르다.

우선순위 큐를 사용해서 각 발전소에서 연결 가능한 도시 중 가중치가 가장 작은 도시를 지속적으로 선택하는 방식으로 구현했다.

import sys
import heapq

n, m, k = map(int, sys.stdin.readline().split())
make_elec = list(map(int, sys.stdin.readline().split()))

routes = [[] for _ in range(n+1)]
visit = [0] * (n+1)

cnt = 0

for _ in range(m):
    v1, v2, cost = map(int, sys.stdin.readline().split())
    routes[v1].append((v2, cost))
    routes[v2].append((v1, cost))

hq =[]
for v in make_elec:
    visit[v] = 1
    cnt += 1
    for vv, cost in routes[v]:
        if visit[vv] != 0:
            continue
        heapq.heappush(hq, (cost, vv))

total_cost = 0
while cnt < n:
    cost, v = heapq.heappop(hq)
    if visit[v] != 0:
        continue
    total_cost += cost
    visit[v] = -1
    cnt += 1
    for vv, cost in routes[v]:
        if visit[vv] != 0:
            continue
        heapq.heappush(hq, (cost, vv))
print(total_cost)

 

 

 

 

크루스칼 알고리즘은 가장 가중치가 작은 간선을 순차적으로 선택하는 탐욕적 방법에 속하는 알고리즘이다.

이때 사이클이 생기지 않게 주의해야 한다. Union Find 알고리즘을 사용해서 구현을 할 수 있다.

먼저 발전소를 하나로 연결한다면 쉽게 답을 구할 수 있다.

 

import sys
sys.setrecursionlimit(10**6)

n, m, e = map(int, sys.stdin.readline().split())

p = [i for i in range(n+1)]
elec = list(map(int, sys.stdin.readline().split()))
for v in elec: p[v] = 0

def find(v):
    if v == p[v]: return v
    p[v] = find(p[v])
    return p[v]

def union(v1, v2):
    r1, r2 = find(v1), find(v2)
    p[max(r1, r2)] = min(r1, r2)

lines = []

for _ in range(m):
    v1, v2, c = map(int, sys.stdin.readline().split())
    lines.append((c, v1, v2))

lines.sort()

cost = 0
for c, v1, v2 in lines:
    if find(v1) == find(v2): continue
    union(v1, v2)
    cost += c
print(cost)

 

---

 

MST 대표 알고리즘인 프림 알고리즘과 크루스칼 알고리즘을 모두 공부할 수 있던 좋은 문제이다.