백준 7044 : Bad Cowtractors (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

for i in range(M):

    A,B,C=map(int,input().split())

    edge.append((C,A,B))

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

        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,M=map(int,input().split())

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

for i in range(M):

    A,B,C=map(int,input().split())

    Tree[A].append((C,B)) #가중치 먼저
    Tree[B].append((C,A))


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

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))

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

📌 어떻게 접근할 것인가?

문제에서 요구하는 것은 최대 스패닝 트리입니다. 두 노드와 연결된 간선의 가중치가 주어졌을때

트리를 연결하면서 가중치의 합이 최대로 만들면 됩니다.

이는 최소 스패닝 트리 알고리즘을 사용하였습니다.

크루스칼 알고리즘에서는 간선의 가중치를 오름차순이 아니라 내림차순으르 정렬했고
프림 알고리즘에서는 최대 힙을 사용하였습니다.

그리고 만약 트리를 만들 수 없다면 $-1$ 을 출력합니다.

크루스칼 알고리즘에서는 판별을

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)

위 코드로 집합이 여러개인지 1개인지에 따라 트리인지 판별 가능하고 프림알고리즘은

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

방문하지 못한 노드가 있는지에 따라서 트리인지 판별이 가능합니다.