백준_1647_도시 분할 계획

문제

1647번: 도시 분할 계획

풀이

1) 크루스칼 알고리즘

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

1. 간선을 비용이 적은 것부터 오름차순으로 정렬한다.

2. 각 간선이 사이클을 발생시키는지 확인한다.

2-1. 사이클을 발생시키지 않는다면 신장 트리에 포함한다.

2-2. 사이클을 발생시키지 않는다면 신장 트리에 포함하지 않는다.

그래프를 둘로 나누어야 하므로, 선택된 간선 중에 유지 비용이 제일 큰 간선 하나를 제거한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M = map(int, input().split())
stack = list()
for _ in range(M):
    n, m, v = map(int, input().split())
    stack.append((v, n, m))

## union & find
parent = [i for i in range(N + 1)]

def find(n):
    if parent[n] == n: return n
    parent[n] = find(parent[n])
    return parent[n]

def join(n, m):
    n = find(n)
    m = find(m)
    parent[max(n, m)] = min(n, m)

## Kruskal
result = 0
maxWeight = 0
stack.sort()
for v, n, m in stack:
    if find(n) != find(m):  # 사이클이 발생하지 않는 경우에만
        join(n, m)
        result += v
        maxWeight = max(maxWeight, v)  # 선택된 간선 중 최대 비용을 저장

print(result - maxWeight)  # 그래프를 둘로 나누므로, 가장 큰 값을 제거