백준 1414 : 불우이웃돕기 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a>b:
        disjoint[a]=b
    else:
        disjoint[b]=a

N=int(input())
String=[ list(input().rstrip()) for _ in range(N) ]
disjoint=[ _ for _ in range(N+1) ]

edge=[] ; total=0

for i in range(N):
    for j in range(N):

        if String[i][j]==0:
            edge.append((0,i+1,j+1))
        else:
            if ord('a')<=ord(String[i][j])<=ord('z'):

                edge.append((ord(String[i][j])-ord('a')+1 , i+1 , j+1))
                total+=ord(String[i][j])-ord('a')+1

            elif ord('A')<=ord(String[i][j])<=ord('Z'):

                edge.append((ord(String[i][j])-ord('A')+27 , i+1,j+1))
                total+=ord(String[i][j])-ord('A')+27

edge.sort(key=lambda x:x[0])

for value,x,y in edge:

    if value==0:
        continue

    if Find(x)!=Find(y):
        Union(x,y)
        total-=value

check=set()
for i in range(1,N+1):
    if Find(i) not in check:
        check.add(Find(i))

if len(check)==1:
    print(total)
else:
    print(-1)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

N=int(input())

String=[ list(input().rstrip()) for _ in range(N) ]
Tree=[ [] for _ in range(N+1) ] ; total=0


for i in range(N):
    for j in range(N):
        if ord('a') <= ord(String[i][j]) <= ord('z'):

            weight = ord(String[i][j]) - ord('a') + 1
            Tree[i].append((weight,j)) #가중치 먼저
            Tree[j].append((weight,i))

        elif ord('A') <= ord(String[i][j]) <= ord('Z'):

            weight = ord(String[i][j]) - ord('A') + 27
            Tree[i].append((weight,j)) #가중치 먼저
            Tree[j].append((weight,i))
        else:
            weight = 0
        if weight != 0:
            total += weight

heap=[(0,0)] ; visit=[False]*(53)

while heap:

    value,node=heapq.heappop(heap)

    if not visit[node]:
        visit[node]=True
        total-=value

        for i,j in Tree[node]:
            heapq.heappush(heap,(i,j))



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

📌 어떻게 접근할 것인가?

최소 스패닝 트리 문제이므로 크루스칼과 프림 알고리즘을 사용했습니다.

처음에 문제를 이해하지 못했는데 그래프가 주어지면

$i$,$j$ 값의 좌표가 $K$ 라면 $i$ 번째 노드와 $j$ 번째 노드는 가중치가 $K$ 인 간선으로 연결되어있다는 말이었습니다.

따라서 아스키 코드값에 따라서 가중치와 좌표값을 입력받고 전체 가중치의 합 - 최소 가중치 를 구해서 최대 가중치를 구했습니다.