[백준] 불우이웃돕기

https://www.acmicpc.net/problem/1414

1414번: 불우이웃돕기

1. 문제 이해

각각의 컴퓨터끼리 랜선으로 연결되어 있고 각각의 랜선은 길이가 있습니다. 다솜이가 가진 컴퓨터가 모두 연결된 상태를 유지하면서 필요 없는 랜선들은 기부하고자 할 때 기부할 수 있는 랜선 길이의 최댓값을 구하는 문제입니다.

2. 문제 접근

첫번째 접근: 최소 스패닝 트리

컴퓨터가 모두 연결되어 있어야하고 연결되어 있기 위해 필요한 최소한의 간선만을 유지하고 나머지 랜선은 기부하면 되므로 크루스칼을 활용한 최소 스패닝 트리에 필요한 간선의 길이를 구하여 전체 랜선 길이에서 빼주면 정답이 되게 됩니다. 연결되어 있지 않은 그래프가 주어지기도 하는데 n - 1개의 간선을 선택할 수 없으면 연결된 그래프가 아니므로 -1을 출력해주면 됩니다.

 

3. 풀이

import sys
from collections import defaultdict

sys.stdin = open("input.txt", "r")

n = int(input())

graph = defaultdict(list)

adj = [
    list(input().rstrip())
    for _ in range(n)
]

# 전체 랜선의 길이
total = 0

edges = []

for i in range(n):
    for j in range(n):
        ch = adj[i][j]
        length = 0

        if ord('A') <= ord(ch) <= ord('Z'):
            length = ord(ch) - ord('A') + 27
            graph[i].append((j, length))
            edges.append((length, i, j))
        elif ord('a') <= ord(ch) <= ord('z'):
            length = ord(ch) - ord('a') + 1
            graph[i].append((j, length))
            edges.append((length, i, j))
        total += length

parent = [
    x for x in range(n + 1)
]

edges.sort()

def find(p):
    if p == parent[p]:
        return p

    parent[p] = find(parent[p])
    return parent[p]

sum_of_edge = 0
cnt = 0

for w, a, b in edges:
    if cnt == n - 1:
        break

    pa = find(a)
    pb = find(b)

    if pa == pb:
        continue

    sum_of_edge += w
    cnt += 1

    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb

# n - 1개의 간선을 택하지 못했으면 연결된 그래프가 아니다.
if cnt == n - 1:
    print(total - sum_of_edge)
else:
    print(-1)