[BOJ/백준] 1368 물대기

import sys
import heapq
input = sys.stdin.readline



N = int(input())
node_list = []
pay_list = []

for i in range(N):
    pay = int(input())
    heapq.heappush(node_list,(pay,i))
    pay_list.append(pay)


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

result = 0
visited = [False]*N
while node_list:
    pay,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += pay

    for next_node in range(N):
        if next_node != node:
            if pay_list[next_node] > connect_list[node][next_node]:
                pay_list[next_node] = connect_list[node][next_node]
                heapq.heappush(node_list,(pay_list[next_node],next_node))


print(result)

이 문제는 MST 문제로 기존의 MST와 다르게 여러개의 출발점을 동시에 가지는 MST라고 생각을 했다.

 

각 출발지점에 따라, 다른거이기 때문에 프림 알고리즘을 크루스칼 알고리즘보다 먼저 생각했다.

 

그래서 각 출발지점을 전부 입력으로 주어진 우물 개설비용으로 초기화 시켜준 점이 기존의 프림알고리즘하고

 

다른 방식이었다.

 

그리고 우물을 파는 비용,논의 위치를 heapq에 넣은듯 프림알고리즘을 해주었다.

 

그리고 방문 표시를 해서, 한번 들린곳은 다시 들리지 않도록 예외 처리를 해줬다.

 

기존의 MST에서 1곳의 출발지점을 정했던것과 달리, 모든 곳을 출발지점으로 생각하고, 비용을 갱신하면 되는 문제였다.

 

 

import sys

input = sys.stdin.readline

N = int(input())
edge = []
cost = []
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]


def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)

    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
    cost.append(pay)

arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))



make_set = [i for i in range(N+1)]
rank = [0 for _ in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)

크루스칼을 활용한 풀이이다.

 

여기서도 기존의 MST와 비슷하지만, 다른점은 물이 생성을 하는곳을 0이라는 인덱스를 부모로 가지도록

 

설정을 해주었다. 우물을 파서, 공급을 받는 곳은, 위치가 다를지라도, 물을 공급받고 있는 것이기 때문에

 

하나의 집합이라고 볼수 있기 때문이다. 이와 같은 작업을 N개가 이어질때까지 반복해주면 된다.

 

 

이 문제는 사실 https://boj.kr/10423 의 문제와 거의 동일하다고 볼 수 있다.