접근 연결된 그래프를 분할하고,그 가중치 합의 최솟값을 구해내는 문제다. 보자마자 당연히 먼저 든 생각은 다익스트라를 떠올렸지만, 그럼 마을을 분할하는 과정을 접근하기 쉽지않다. 그 다음에 든 생각은 저번에 풀었던 2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) 이 문제의 알고리즘인 크루스칼 알고리즘이 떠올랐다. 최소 스패닝 트리는 모든 노드를 연결하는 엣지들의 최소 가중치를 찾는 문제다. 그럼 모든 노드를 연결짓는 최소 가중치를 찾고, 나머지 하나 가장 큰 가중치의 엣지를 제거하면 되겠네? 라는 흐름으로 이어졌다. 해결 위에 언급했던대로, 크루스칼 알고리즘을 사용하여 쉽게 해결했다. 근데 처음 과정은 가장 큰 가중치 하나를 찾고, M..