백준 1922 : 네트워크 연결 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

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

    return disjoint[x]

N=int(input())
M=int(input())

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

edge=[ list(map(int,input().split())) for _ in range(M) ]

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

total=0

for x,y,value in edge:

    x=Find(x)
    y=Find(y)

    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        total+=value

print(total)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

N=int(input())
M=int(input())

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)) #가중치를 먼저


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

while heap:

    value,node=heapq.heappop(heap)

    if not visit[node]:

        total+=value
        visit[node]=True
        
        for i,j in Tree[node]:
            heapq.heappush(heap,(i,j))

print(total)

📌 어떻게 접근할 것인가?

최소 스패닝 트리 기초 문제입니다. 크루스칼과 프림 알고리즘을 이용하여 풀었습니다.

그대로 구현해주시면 됩니다. 다만 프림 알고리즘 사용시 첫 노드의 번호는 1 이기 때문에
$(0,1)$ 을 넣어주셔야합니다.