Algorithm/Mst1 [백준] 1647번 도시 분할 계획 _ Python https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. Preview 시간 복잡도: O(M*logM) 공간 복잡도: O(M) 참고 : - 유형: MST 2. 초기 접근 방법 MST(Minimum Spanning Tree) 알고리즘 그래프 내의 모든 정점을 포함하는 트리를 구성하는데, 구성 간선들의 가중치 합의 최소를 목표로 한다. 프림 알고리즘 : 방문한 노드의 미방문 노드 간선들 중 최소 간선을 선택 - .. 2024. 4. 11. 이전 1 다음