MST, 프림
1. 값을 인접리스트로 받는다(양방향)
2. q에 초기값을 놓고(아무 노드) q가 빌때까지
- 현재 그래프에 연결이 안된 경우에만 (connected == False)
- 연결을 해주고(connected == True) total에 비용(cost) append
- 인접리스트를 for문으로 돌면서 연결이 안된 노드만 heapq에 heappush
3. max_value = total에서 가장 큰 값
4. 마을을 두곳으로 나눠야 해서 가장 비용이 큰 max_value를 sum(total)에서 빼준다.
MST문제이며 크루스칼알고리즘으로도 풀 수 있다.
프림알고리즘으로 풀었다.
'Algorithm > BOJ' 카테고리의 다른 글
| [백준] 2638번 - 치즈 (파이썬) (0) | 2022.01.22 |
|---|---|
| [백준] 1600번 - 말이 되고픈 원숭이 (파이썬) (0) | 2022.01.21 |
| [백준] 12581번 - 숨바꼭질 2 (파이썬) (0) | 2022.01.21 |
| [백준] 17142번 - 연구소 3 (파이썬) (0) | 2022.01.20 |
| [백준] 4485번 - 녹색 옷 입은 애가 젤다지? (파이썬) (0) | 2022.01.20 |
