[BOJ] 1647번 : 도시 분할 계획(MST, Kruskal)

접근

연결된 그래프를 분할하고,그 가중치 합의 최솟값을 구해내는 문제다.

보자마자 당연히 먼저 든 생각은 다익스트라를 떠올렸지만, 그럼 마을을 분할하는 과정을 접근하기 쉽지않다.

그 다음에 든 생각은 저번에 풀었던

2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal)

이 문제의 알고리즘인 크루스칼 알고리즘이 떠올랐다.

 

최소 스패닝 트리는 모든 노드를 연결하는 엣지들의 최소 가중치를 찾는 문제다.

그럼 모든 노드를 연결짓는 최소 가중치를 찾고, 나머지 하나 가장 큰 가중치의 엣지를 제거하면 되겠네? 라는 흐름으로 이어졌다.

 

해결

위에 언급했던대로, 크루스칼 알고리즘을 사용하여 쉽게 해결했다.

근데 처음 과정은 가장 큰 가중치 하나를 찾고, MST에서 빼준 방식으로 풀었는데 생각해보니까 엣지들을 가중치 기준으로 오름차순으로 찾아나가는데, 왜 이걸 하고있지? 라는 생각이 들었다.

그래서 원래 크루스칼 알고리즘은 포함된 간선의 갯수가 '노드의 갯수 - 1' 이 되면 정지하는데, 그냥 '노드의 갯수 - 2'일 때 정지하면, 자동으로 가장 큰 가중치의 엣지는 포함되지 않을까라는 판단으로 코드를 수정해서 제출했더니 맞았다.

 

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
edges = []
for _ in range(M):
    u, v, w = map(int, input().split())
    edges.append((w, (u, v)))
    
edges = sorted(edges, key=lambda x : x[0])
parents = [i for i in range(N+1)]

def find(x):
    if parents[x] == x:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    parents[y] = x
    

spanning_dist = 0
e_num = 0
# max_edges = 0
for w, (a, b), in edges:
    if e_num == N-2:
        break
        
    if find(a) != find(b):
        spanning_dist += w
        # max_edges = max(max_edges, w)
        e_num += 1
    
    union(a, b)
    
    
        
print(spanning_dist)