[백준] 10423 전기가 부족해

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

발전소가 존재하는 도시에서 출발하여, 다른 도시로 전기가 제공되기 위해 케이블을 설치해야 했습니다.

케이블 설치 비용이 적게 하여 설치가 필요하여, 가중치를 고려하여야 했습니다.

케이블 설치 비용을 적은 것부터 탐색하여 설치하기 위하여 최소힙을 이용하였습니다.

 

발전소가 있는 도시들을 모두 최소힙에 넣어두고, 탐색을 시작하였습니다.

다음으로 연결된 도시를 케이블의 가중치와, 연결된 도시의 번호를 최소힙에 추가하였고, 케이블 설치 비용이 낮은것부터 설치하도록 하였습니다.

2) 알고리즘

• 최소 신장 트리
• 최소힙

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')

def solution(h):
    while h:
        w, n = heapq.heappop(h)                         # 가중치, 도시 번호
        if visited[n] == -1:                            # 전기가 연결되어 있지 않으면
            visited[n] = w                              # 사용한 케이블 가중치 기록
            for next in linked[n]:                      # 연결된 도시들
                heapq.heappush(h, (next[0], next[1]))   # 케이블 가중치, 다음 도시 번호


N, M, K = map(int, sys.stdin.readline().split())        # 도시, 케이블, 발전소 수
station = list(map(int, sys.stdin.readline().split()))  # 발전소 도시들 리스트
linked = [[] for _ in range(N)]                         # 도시간 연결 케이블 정보
visited = [-1] * N                                      # 도시들 전기 연결 여부

h = []                                                  # 최소 힙
for s in station:                                       # 발전소가 있는 도시들
    heapq.heappush(h, (0, s-1))                         # 가중치 0으로 처음 전기가 시작 되는곳

for _ in range(M):
    u, v, w = map(int, sys.stdin.readline().split())

    linked[u-1].append((w, v-1))                        # 케이블은 양방향으로 설치 가능하여
    linked[v-1].append((w, u-1))                        # 두개의 도시에 연결 정보 추가

solution(h)                         # 탐색

print(sum(visited))                 # 도시 케이블 연결된 가중치 합

---

🔗 문제 링크

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

10423번: 전기가 부족해

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다