미소를뿌리는감자의 코딩
[백준 2024/02/19] 16398번 행성 연결 본문
728x90
https://www.acmicpc.net/problem/16398
1. 접근 방법
이번 문제는 일반적인 최소 신장 트리를 이용하는 문제이다.
단지, weight들이 행렬로 제공되었다는 점에서 다르다.
일단, prim's algorithm에 대한 설명은 아래에 자세히 적어놓았다.
https://potatoscatteringsmile.tistory.com/112
이제 이번 문제에서 자세히 다루어 볼 점은 행렬로 제공된 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)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/20] 20055번 컨베이어 벨트 위의 로봇 (0) | 2024.02.20 |
---|---|
[백준 2024/02/20] 1244번 스위치 켜고 끄기 (0) | 2024.02.20 |
[백준 2024/02/19] 1647번 도시 분할 계획 (1) | 2024.02.19 |
[백준 2024/02/19] 13905번 세부 (0) | 2024.02.19 |
[백준 2024/02/17] 1068번 트리 (0) | 2024.02.17 |