[백준] 1414번 - 불우이웃돕기

---

문제 분석

인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 필요하다.
먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다.
이때 i와 j가 같은 곳의 값은 같은 컴퓨터를 연결한다는 의미이므로 별도 에지로 저장하지 않고 나머지 위치의 값들을 i->j로 가는 에지로 생성하고, 에지리스트에 저장하여 최소 신장 트리로 해결하며 된다.
즉, 총 나올수 있는 랜선의 길이 - 최소로 가능한 랜선의 길이 를 통해 문제를 해결하면 된다.

---

소스 코드

# 불우이웃돕기

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N = int(input())
D = [0] * (N + 1)
for i in range(1, N + 1):
    D[i] = i
queue = PriorityQueue()
edgeNum = 0
totalSum = 0
tempValue = 0

for i in range(1, N + 1):
    numList = list(input())
    for j in range(1, len(numList)):
        value = 0
        if ord(numList[j-1]) >= ord('a') and ord(numList[j-1]) <= ord('z'):
            value = ord(numList[j-1]) - ord('a') + 1
        elif ord(numList[j-1]) >= ord('A') and ord(numList[j-1]) <= ord('Z'):
            value = ord(numList[j-1]) - ord('A') + 27
        if i == j:
            totalSum += value
            continue
        totalSum += value
        queue.put((value, i, j))


def find(idx):
    if idx == D[idx]:
        return idx
    else:
        D[idx] = find(D[idx])
        return D[idx]


success = True

while edgeNum < N - 1:
    if queue.empty():
        success = False
        break
    w, s, e = queue.get()
    if w != 0 and find(s) != find(e):
        tempValue += w
        edgeNum += 1
        D[find(s)] = D[find(e)]

if not success:
    print(-1)
else:
    print(totalSum - tempValue)