[BOJ/백준] 16398 행성 연결

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()


N = int(input())

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

node_list = []

INF = float('inf')
distance_list = [INF for _ in range(N)]
visited = [False for _ in range(N)]
heapq.heappush(node_list,(0,0))
distance_list[0] = 0
result = 0
while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)
    if visited[cur_node]:continue
    if cur_dis > distance_list[cur_node]:continue
    result += cur_dis
    visited[cur_node] = True
    for next_node in range(N):
        if next_node == cur_node:continue
        if visited[next_node]:continue
        if distance_list[next_node] > graph[cur_node][next_node]:
            distance_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(distance_list[next_node],next_node))

print(result)

 프림 알고리즘

 

 

import sys

def input():
    return sys.stdin.readline().rstrip()

def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False



N = int(input())
edge_list = []
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(N):
        if x == y:continue
        edge_list.append((temp[y],x,y))


edge_list.sort(reverse=True)

cnt = 1
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]
result = 0
while cnt <N:
    dis,node_a,node_b = edge_list.pop()
    if union(node_a,node_b):
        cnt += 1
        result += dis

print(result)

 

크루스칼 알고리즘

 

 

전형적인 MST 문제이다. MST 문제를 푸는 방식대로 풀면 된다.