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

💡문제접근

• 문제에 대한 이해가 늦어 풀이에 많은 시간이 걸렸던 문제였다.

💡코드(메모리 : 31256KB, 시간 : 48ms)

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N = int(input())
lst = [list(input().strip()) for _ in range(N)]
parent = [0] * (N+1)
edges = []
result = 0

# 부모 테이블을 자기 자신으로 초기화
for i in range(1, N+1):
    parent[i] = i

for a in range(N):
    for b in range(N):
        if lst[a][b] == "0":
            edges.append([0, a, b])
        else:
            if 'a' <= lst[a][b] <= 'z':
                cost = ord(lst[a][b]) - 96
                result += cost
            elif 'A' <= lst[a][b] <= 'Z':
                cost = ord(lst[a][b]) - 38
                result += cost
            if a != b:
                edges.append([cost, a, b])
edges.sort()
for edge in edges:
    cost, a, b = edge
    # 랜선이 없음
    if cost == 0:
        continue
    # 두 노드의 부모가 같지 않은 경우에만 연결을 수행
    # 간선을 발생시키지 않는 경우에만 간선을 추가하는 MST 알고리즘
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        # 해당 비용 차감
        result -= cost

for i in range(1, N+1):
    find_parent(parent, i)

# 크루스칼 알고리즘을 돌고 난 후 모든 노드에 대해서 find를 수행한 후에 양 옆의 노드 부모가 같지 않다면>
# 연결이 되지 않은 경우이므로 이런 경우 -1을 출력
for i in range(N-1):
    if parent[i] != parent[i+1]:
        print(-1)
        sys.exit(0)
print(result)

💡소요시간 : 1h 24m