새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 10423 전기가 부족해

by 언호 2022. 7. 7.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 전기가 부족해

첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 15685 드래곤 커브  (0) 2022.07.09
[백준] 18436 수열과 쿼리 37  (0) 2022.07.08
[백준] 2623 음악프로그램  (0) 2022.07.06
[백준] 2660 회장뽑기  (0) 2022.07.05
[백준] 1516 게임 개발  (0) 2022.07.04

댓글