백준 21924 : 도시 건설 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

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

    return disjoint[x]

N,M=map(int,input().split())

disjoint=[ _ for _ in range(N+1) ]

edge=[] ; total=0 ; check=0

for i in range(M):

    a,b,c=map(int,input().split())
    edge.append((c,a,b))
    total+=c

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

for value,x,y in edge:

    x=Find(x)
    y=Find(y)
    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        check+=value

tmp=set()
for i in range(1,N+1):

    if Find(i) not in tmp:
        tmp.add(i)

if len(tmp)>1:
    print(-1)
else:
    print(total-check)    

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

N,M=map(int,input().split())

Tree=[ [] for _ in range(N+1) ]

visit=[False]*(N+1) ; check=0 ; total=0 ; heap=[(0,1)]

for i in range(M):
    a,b,c=map(int,input().split())

    Tree[a].append((c,b)) # 가중치 먼저
    Tree[b].append((c,a))
    total+=c

while heap:

    value,node=heapq.heappop(heap)

    if not visit[node]:

        visit[node]=True
        check+=value

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

if visit[1:].count(False)>=1:
    print(-1)
else:
    print(total-check)

📌 어떻게 접근할 것인가?

최소 스패닝 트리 문제입니다. 그대로 구현해주면 되지만 문제에서 주의해야할 점은 모든 노드가 연결되어있는지 판별해주어야 합니다.

tmp=set()
for i in range(1,N+1):

    if Find(i) not in tmp:
        tmp.add(i)

if len(tmp)>1:
    print(-1)
else:
    print(total-check)  

크루스칼 알고리즘에서는 집합이 2개이상으로 분리되어있는지 체크를 통해 판별가능합니다.

if visit[1:].count(False)>=1:
    print(-1)
else:
    print(total-check)

프림은 visit 배열을 사용하면서 False 값의 개수에 따라서 모든 노드를 방문했는지 판별 가능합니다.

나머지는 $MST$ 알고리즘을 그대로 구현해주면 됩니다.