백준 1647번 - 도시 분할 계획

도시 분할 계획 문제 바로 가기

풀이 날짜: 2026-03-18

baekjoon 알고리즘 문제 풀이

풀이 코드


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

v,e = map(int, input().split())
parent = [0] * (v+1)
edge = []
result = 0

for i in range(1,v+1):
    parent[i] = i

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

edge.sort()
answer = 0

for i in edge:
    cost,a,b = i
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent, a, b)
        result += cost
        answer = cost

print(result - answer)

접근 방법

이 문제는 단순히 최소 비용으로 모든 집을 연결하는 것이 아니라, 하나의 마을을 두 개의 마을로 분리하면서 유지 비용을 최소로 만드는 것이 목표이다. 따라서 먼저 모든 집을 최소 비용으로 연결하는 최소 스패닝 트리(MST)를 만든 뒤, 그 구조에서 하나의 간선을 제거하는 방식으로 접근해야 한다.

최소 스패닝 트리(MST) 구성

최소 스패닝 트리는 모든 노드를 연결하면서도 간선의 총 비용이 최소가 되도록 구성한 트리이다. 이를 위해 Kruskal 알고리즘을 사용하였다. 간선을 비용 기준으로 오름차순 정렬한 뒤, 사이클이 발생하지 않는 경우에만 간선을 선택하여 트리를 확장해 나간다. 이 과정에서 Union-Find(Disjoint Set)를 활용하여 사이클 여부를 효율적으로 판단했다.

Union-Find 사용 이유

Union-Find 자료구조는 각 노드가 어떤 집합에 속해 있는지를 빠르게 확인하고, 두 집합을 합치는 연산을 효율적으로 수행할 수 있게 해준다. 특히 Kruskal 알고리즘에서는 간선을 추가할 때 두 노드의 부모가 같은지 확인하여 사이클 발생 여부를 판단하는데, 이때 경로 압축을 적용한 find 연산을 사용하면 시간 복잡도를 크게 줄일 수 있다.

마을을 두 개로 나누는 핵심 아이디어

이 문제의 핵심은 최소 스패닝 트리를 만든 이후, 가장 비용이 큰 간선을 제거하는 것이다. 최소 스패닝 트리는 이미 전체 연결 비용이 최소인 상태이므로, 여기서 임의의 간선을 제거하면 두 개의 연결된 그래프로 나뉘게 된다. 이때 가장 비용이 큰 간선을 제거해야 전체 비용 감소 효과가 가장 크기 때문에, 결과적으로 두 마을의 유지 비용을 최소로 만들 수 있다.

코드에서 result와 answer의 의미

코드에서 result는 최소 스패닝 트리를 구성하면서 선택된 모든 간선 비용의 합을 의미한다. 반면 answer는 마지막에 추가된 간선의 비용을 저장하는데, 이는 간선이 비용 오름차순으로 정렬되어 있기 때문에 결국 MST에서 가장 큰 비용의 간선이 된다. 따라서 result - answer는 전체 MST 비용에서 가장 큰 간선을 제거한 값으로, 문제에서 요구하는 최종 최소 유지 비용이 된다.

내가 헷갈렸던 부분

처음에는 result += cost와 answer = cost, 그리고 마지막의 result - answer가 왜 필요한지 이해가 되지 않았다. 특히 answer를 단순히 마지막 간선의 비용으로 저장하는 코드가 직관적으로 와닿지 않았고, 왜 그 값을 빼야 하는지도 혼란스러웠다.

이후 흐름을 다시 따라가면서 이해하게 된 점은, 간선을 비용 기준으로 오름차순 정렬한 뒤 Kruskal 알고리즘을 적용하면 최소 스패닝 트리에서 간선이 작은 비용부터 순서대로 선택된다는 것이다. 따라서 가장 마지막에 선택되는 간선은 자연스럽게 MST에서 가장 비용이 큰 간선이 된다.

즉, answer = cost는 단순히 마지막 값을 저장하는 것이 아니라, “현재까지 선택된 간선 중 가장 큰 비용”을 의미하게 된다. 그리고 문제에서 요구하는 것은 하나의 마을을 두 개로 나누는 것이기 때문에, MST에서 간선 하나를 제거해야 한다. 이때 가장 비용이 큰 간선을 제거하는 것이 전체 유지 비용을 최소로 만드는 방법이다.

결국 result는 MST 전체 비용이고, answer는 그중 가장 큰 간선 비용이므로, result - answer는 해당 간선을 제거한 뒤의 최소 비용을 의미하게 된다. 이 흐름을 이해하고 나니 코드가 단순한 트릭이 아니라 문제의 핵심 아이디어를 그대로 구현한 것이라는 것을 알게 되었다.

Vienna sausage