[백준] 6497 전력난

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

마을마다 모두 하나씩 길이 연결되어 있어야하고, 그 길의 유지비용이 가장 적게 할 수 있는 경우를 구해야 하므로 '최소 신장 트리' 알고리즘으로 접근

2) 알고리즘

• 최소 신장 트리 (Minimum Spanning Tree)

3) 풀이 코드

사용 언어 - Python

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


def kruskal(start):                                     # 힙을 이용한 크루스칼 알고리즘 구현
    global min_cost

    heap = [(0, start)]                                 # 최초 시작 지점 초기화

    while heap:
        node = heapq.heappop(heap)
        if not visited[node[1]]:                        # 아직 연결되지 않은 도착지인 경우
            visited[node[1]] = 1                        # 방문 처리
            min_cost += node[0]                         # 길이 연결되었으므로 유지 비용 추가
            for e in linked[node[1]]:                   # 길의 길이를 기준으로 하여 최소힙 
                heapq.heappush(heap, (e[0], e[1]))


while True:
    M, N = map(int, sys.stdin.readline().split())       # 집의 개수, 길의 개수
    linked = [[] for _ in range(M)]                     # 집들의 연결 관계 리스트
    visited = [0] * M                                   # 해당 집 방문 여부 저장하는 리스트
    total_cost = 0                                      # 모든 길을 연결했을때 드는 비용
    min_cost = 0                                        # 모든 집을 연결하는데 드는 최소한의 비용

    if not sum((M, N)):                                 # 테스트 케이스 종료
        break

    for _ in range(N):
        x, y, z = map(int, sys.stdin.readline().split())    # 출발 집, 도착 집, 길의 길이
        total_cost += z                                     # 길의 유지비용 추가
        linked[x].append((z, y))                            # 양방향으로 집 연결 관계 추가
        linked[y].append((z, x))

    kruskal(0)                                              # 0번 집부터 크루스칼 시작

    print(total_cost - min_cost)                            # 절약할 수 있는 최대 비용

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다

2) 새롭게 학습한 내용

특별히 없습니다

---

🔗 문제 링크

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

6497번: 전력난

 

 

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