백준/ Gold 2 문제 , 백준 파이썬 10423 , 전기가 부족해 [최소 스패닝 트리, 프림 알고리즘]

백준/ Gold 2 문제 , 백준 파이썬 10423 , 전기가 부족해 [최소 스패닝 트리, 프림 알고리즘]

 

 

풀이 시간

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

 

 

문제 출처

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

10423번: 전기가 부족해

 

 

풀이

 

발전소가 최소 한개이상은 연결이 되어야하기때문에 발전소가 설치된 노드들은 0의 가중치를 가진채로 graph의 0번인덱스에 저장시켜놓고 시작지점을 0번노드부터 돌린다. 이렇게되면 무조건 한개 이상의 발전소가 생기게되며, 최소 가중치를가진 발전소부터 최소 스패닝 트리를 만들어 나가게 된다. 

 

이후 케이블이 발전소에도 이어진 간선들이 있기때문에 그 간선이 최소 가중치를 갖는다면 다른 발전소도 다른 노드에 연결될 수 있다.

 

만약 연결이 안되는 발전소가 있더라도 굳이 연결될 필요가 없으므로 문제 없다.

 

이렇게 최종 최소 스패닝 트리가 완성되면 결과값을 출력시켜주면 된다.

 

 

 

 

 

 

 

정답

 

 

import heapq
import sys
input=sys.stdin.readline

N,M,K=map(int,input().split())
e=list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
for i in e:
    graph[0].append((0,i))
for i in range(M):
    u,v,w=map(int,input().split())
    graph[u].append((w,v))
    graph[v].append((w,u))
    
visited=[True]+[False]*(N)
q=graph[0]
heapq.heapify(q)
result=0

while q:
    Z,X=heapq.heappop(q)
    if not visited[X]:
        visited[X]=True
        result+=Z
        for i in graph[X]:
            if not visited[i[1]]:
                heapq.heappush(q,i)    
            
print(result)