[백준] 1647 도시분할 계획

문제

• 마을에는 N개의 집과 그 집을 연결하는 M개의 길이 있고, 그 길마다 길을 유지하는데 드는 유지비가 있다.
  • 2 <= N <= 100,000
  • 1 <= M <= 1,000,000
• 마을의 이장은 마을을 2개로 분할할 계획을 세우고 있다.
• 각 분리된 마을 안에 1개 이상의 집이 있어야 하고 각 집들은 서로 연결되어야 한다.
• 길의 유지비 합의 최소는? 

 

풀이

• 최소 신장 트리 2개 만들기!
  • 크루스칼 알고리즘으로 최소 신장 트리 찾고, 가장 비용이 큰 간선 제거하기
  • 가장 비용이 큰 간선은 결국 가장 마지막에 추가된 간선이다.
• 시간 복잡도 : O(M logM) = 약 20,000,000 가능하다!

 

import sys
input = sys.stdin.readline

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 입력 받기
N, M = map(int, input().split())
parent = [0] * (N+1)
for i in range(1, N+1):
    parent[i] = i

edges = []          # 간선 정보
result = 0          # 유지비 합
mst = []            # 포함된 간선 비용

for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

edges.sort()

# 간선 하나씩 확인
for edge in edges:
    cost, a, b = edge
    # 사이클 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        mst.append(cost)


print(result - mst[-1])

 

References

• '이것이 코딩테스트다' ch10 그래프 이론 - 도시 분할 계획
• 백준 1647번