내가보려고만든 메자노트

문제 보러 가기 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 이 문제는 MST(최소 신장(스패닝) 트리)를 이용하여 풀 수 있었다. 크루스 칼, 프림 두 개의 알고리즘으로 풀이가 가능했고 나의 경우 프림 알고리즘으로 풀었다. 문제풀이 2개의 도시로 분할해야 하므로 프림 알고리즘을 통해 MST를 만든 후 가장 비용이 높은 간선 하나를 제거하면 2개의 도시로 나눠지고 최소 비용을 구할 수 있다. - 임의의 시작 노드를 Queue에 넣고 연결된 NodeList를 Priori..

최소 스패닝 트리(Minimum Spannig Tree) = 최소 신장 트리 : 스패닝 트리 중 가장 작은 가중치의 간선으로 구성된 트리를 의미한다. 조건 본래의 그래프의 모든 노드를 포함 간선의 가중치의 합이 최소여야 한다 모든 노드가 서로 연결되어있다 트리의 속성을 만족 (사이클이 존재하지 않는다) ↓스패닝 트리란? 더보기 스패닝 트리란? : 그래프의 최소 개수의 간선으로 이뤄진 트리 (n개의 노드가 존재한다면 간선은 항상 n-1개이다) 모든 노드가 연결되어야 함 사이클이 존재하지 않음 즉, 최소 스패닝 트리에서 최소 가중치의 합 조건만 빠진 트리를 의미. 이 최소 스패닝 트리 문제를 다루는 알고리즘에는 2가지가 있다. 1. 크루스 칼(Kruskal) 알고리즘 : 두 노드 간 제일 작은 가중치의 간선..