[BOJ] 1647. 도시 분할 계획

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

1647번: 도시 분할 계획

 

 

1. 해결방법

1. 아이디어
- MST 이용
- 입력하는 a, b ,c를 이용해서 간접리스트에 append
- 힙에 시작점을 저장
- 힙이 빌때까지 다음의 내용을 반복
    - 힙에서 최솟값을 꺼내고 방문 여부를 확인
    - 방문하지 않았다면 인접리스트를 이용해서 인접노드를 힙에 push, 방문했자면 pass
    - 비용을 result에 추가

2. 시간복잡도
- O(MlogM)

3. 자료구조
- 힙 : [비용, 연결 노드]
- 방문 : chk[]
- 인접리스트 : [비용, 연결 노드]
"""

 

 

2. 정답코드

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

edge = [[] for _ in range(N + 1)]
for i in range(M):
    a, b, c = map(int, input().split())
    edge[a].append([c, b])
    edge[b].append([c, a])

heap = [[0, 1]]
result = []
chk = [False] * (N + 1)
longest = 0

while heap:
    w, each_node = heapq.heappop(heap)

    if chk[each_node] == False:
        chk[each_node] = True
        result.append(w)

        if len(result) == N:
            break

        for next_node in edge[each_node]:
            if chk[next_node[1]] == False:
                # 힙에 삽입
                heapq.heappush(heap, next_node)


print(sum(result) - max(result))

MST의 프림 알고리즘을 사용하니 python3로는 시간초과가 나온다..
그래서 pypy3로 했지만 추 후에 코드를 수정해서 시간복잡도를 해결해봐야겠다.