백준 14950 : 정복자 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

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

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

disjoint=[ _ for _ in range(N+1) ]  ; edge=[] ; count=0 ; 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
        count+=1
        total+=value

for i in range(count-1):
    total+=(i+1)*T

print(total)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

N,M,T=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)] #1번노드 먼저
total=0 ; count=0

while heap:

    value,node=heapq.heappop(heap)

    if not visit[node]:
        visit[node]=True
        total+=value
        count+=1

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

for i in range(count-2): # 1번노드는 이미 정복했으므로 -2 
    total+=(i+1)*T

print(total)

📌 어떻게 접근할 것인가?

최소 스패닝 트리 기초 문제입니다. 크루스칼과 프림 알고리즘을 구현해주면 되는데

매번 땅을 정복할때마다 비용에 $T$ 증가하므로 count 변수를 통해 땅을 정복한 개수를 세주고

모든 노드를 연결한 후에 반복문을 통해서 T×1 , T×2 , T×3 ... 연산을 통해 total 변수에 값을 더해주면됩니다.