[백준] 1414 불우 이웃 돕기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1414
• 🔑 최소 비용 신장 트리, 프림 알고리즘
  • 입력되는 문자열을 문제 형식에 맞게 숫자로 변환해서 그래프를 생성한다. ord() 함수 사용
  • 변환한 랜선 길이의 총 합도 구해놓는다.
  • 그리고 프림 알고리즘을 사용해 최소 비용을 구할 때마다 전체 랜선의 길이에서 빼준다.
  • 남은 랜선의 길이가 정답인데 방문을 못한 노드가 있으면 -1을 출력한다.
    • 더 쉬운 프림 알고리즘 문제 : https://study-yoon.tistory.com/235

 

import sys
from heapq import heappop, heappush
from collections import defaultdict

input = sys.stdin.readline

n = int(input())

tree = defaultdict(list)
total = 0   # 들고있는 전체 랜선의 길이

for i in range(n):
    string = input()
    for j in range(n):
        if ord("a") <= ord(string[j]) <= ord("z"):      # 소문자
            dist = ord(string[j]) - ord("a") + 1
            tree[i].append((dist, j))                   # 길이 먼저
            tree[j].append((dist, i))

        elif ord("A") <= ord(string[j]) <= ord("Z"):    # 대문자
            dist = ord(string[j]) - ord("A") + 27
            tree[i].append((dist, j))
            tree[j].append((dist, i))
        else:                                           # '0'
            dist = 0
        if dist != 0:
            total += dist

heap = [(0, 0)]
visit = [False] * (53)  # Z = 52

while heap:
    d, node = heappop(heap)

    if not visit[node]:     # 방문 안했으면
        visit[node] = True  # 방문 처리
        total -= d          # 사용한 랜선 빼주기

        for next_d, next_node in tree[node]:    # 현재 노드랑 연결된 선 정보 추가
            heappush(heap, (next_d, next_node))

for i in range(n):
    if not visit[i]:
        print(-1)
        exit(0)

print(total)