[백준 2024/02/19] 16398번 행성 연결

https://www.acmicpc.net/problem/16398

16398번: 행성 연결

 

1. 접근 방법

이번 문제는 일반적인 최소 신장 트리를 이용하는 문제이다.

단지, weight들이 행렬로 제공되었다는 점에서 다르다.

 

일단, prim's algorithm에 대한 설명은 아래에 자세히 적어놓았다.

https://potatoscatteringsmile.tistory.com/112

[백준 2024/02/13] 1922번 네트워크 연결

 

이제 이번 문제에서 자세히 다루어 볼 점은 행렬로 제공된 weight들을 어떻게 정리할 것인가 이다.

 

우선 대각선의 값들은 0 이라는 특징이 있으며, 대각선을 기준으로 값들이 대칭임을 알 수 있다.

왜냐하면, 1번 노드에서 1번 노드로 이동할 때의 weight 는 0이기 때문이다. 2 -> 2, 3 -> 3 도 동일하다.

 

따라서 위에 값들만 이용해서 weight를 list에 저장해주려고 한다.

특징적으로 볼 수 있는 것은 왼쪽 index값 +1 = 오른쪽 index 값으로 시작한다는 점이다.

 

[1][2] 와 [2][3]을 보면 알 수 있다.

따라서 2중 for 문을 구성하되, 안쪽에 있는 for문은 밖의 index의 +1부터 시작하도록 구성하였다.

for column in range(1, n, 1):
    for row in range(column+1, n+1, 1):

 

이후 weight를 list(map(int, input().split()))으로 받아주었기에, c[row-1]로 값을 찾아주었다. -1을 해준 이유는 index의 경우 0부터 시작하기 때문이다. 따라서 column의 값이 1일 때, index는 0을 받아주어야 한다.

 

2. 코드

import heapq

n = int(input())

node_list = [[] for _ in range(n+1)]
visited = [False] * (n+1)
heap = []
answer = 0
edges = 0

for column in range(1, n, 1):
    c = list(map(int, input().split()))
    for row in range(column+1, n+1, 1):
        node_list[column].append((c[row-1], row))
        node_list[row].append((c[row-1], column))


for (weight, idx) in node_list[1]:
    heapq.heappush(heap, (weight, idx))

visited[1] = True

while edges < n-1:
    weight, idx = heapq.heappop(heap)
    if visited[idx]:
        continue
    visited[idx] = True
    answer += weight
    edges += 1

    for weight, idx in node_list[idx]:
        heapq.heappush(heap, (weight, idx))

print(answer)