1647

날짜 : 2023. 03. 28

사용 언어 : python

 

문제

 

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())  # 집의 개수, edge의 개수
parent = [i for i in range(n + 1)]
edges = []


def parent_find(parent, x):
    if parent[x] != x:
        parent[x] = parent_find(parent, parent[x])
    return parent[x]


def parent_union(parent, a, b):
    a = parent_find(parent, a)
    b = parent_find(parent, b)
    if a < b:  # 부모 : 번호가 더 작은 노드
        parent[b] = a
    else:
        parent[a] = b
    return


total = 0
max_val = 0
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    edges.append([c, a, b])

edges.sort()
for i in range(m):
    cost, start, end = edges[i]
    if parent_find(parent, start) != parent_find(parent, end):  # 서로 부모가 다르면(사이클 x)
        parent_union(parent, start, end)  # 합치기
        total += cost  # 전체 비용 포함
        max_val = max(max_val, cost)  # mst에서 최대 비용 간선 차감(마을 분할)

print(total - max_val)

 

 

풀이

- MST의 Kruskal 알고리즘을 활용해 최소신장 트리를 생성한 후 그 중 가장 큰 cost를 갖고 있는 간선을 차감한다.(마을 분할)

 

 

알게된 점

- Kruskal을 활용한 문제였다.

 

 

참고 사이트

-