[백준 / 1647 / Python] 도시 분할 계획

들어가며

백준 1647번 '도시 분할 계획' 문제는 최소 신장 트리(MST)의 성질을 활용한 흥미로운 문제입니다.

핵심 아이디어는 전체 그래프에서 MST를 만든 후, 가장 비싼 간선 하나를 제거하면 두 개의 연결된 마을로 나눌 수 있다는 점입니다.

---

문제 분석

📋 문제 요약

• 시간 제한: 2초 | 메모리 제한: 256MB | 정답률: 49.164%
• N개의 집과 M개의 길이 있는 마을을 두 개의 마을로 분할
• 각 마을 내에서는 모든 집이 연결되어야 함
• 남은 길의 유지비 합을 최소화

🎯 핵심 통찰

마을을 두 개로 나누기 = MST에서 간선 하나 제거하기

왜 이 방법이 최적일까요?

1. MST는 N-1개의 간선으로 모든 정점을 연결
2. MST에서 간선 하나를 제거하면 정확히 두 개의 트리가 생성
3. 가장 비싼 간선을 제거해야 남은 비용이 최소

---

해결 방법: 크루스칼 알고리즘

🔧 알고리즘 단계

1. 모든 간선을 비용 순으로 정렬
2. 크루스칼 알고리즘으로 MST 구성하면서 가장 비싼 간선 추적
3. MST 총 비용 - 가장 비싼 간선 = 답

💻 구현 코드

import sys
input = sys.stdin.readline

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])  # 경로 압축
    return parent[x]

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())

# 부모 테이블 초기화
parent = [i for i in range(N + 1)]

# 간선 정보 입력 및 정렬
graph = []
for _ in range(M):
    graph.append(list(map(int, input().split())))
graph.sort(key=lambda x: x[2])

result = 0
max_cost = 0

# 크루스칼 알고리즘으로 MST 구성
for start, end, cost in graph:
    if find_parent(start) != find_parent(end):
        union(start, end)
        result += cost
        max_cost = max(cost, max_cost)  # 가장 비싼 간선 추적

# 가장 비싼 간선 제거
print(result - max_cost)

---

예제 동작 과정

📊 입력 데이터

7 12
1 2 3    1 3 2    3 2 1    2 5 2
3 4 4    7 3 6    5 1 5    1 6 2
6 4 1    6 5 3    4 5 3    6 7 4

🔄 MST 구성 과정

1단계: 간선 정렬 (비용 기준)

(3,2):1  (6,4):1  (1,3):2  (1,6):2  (2,5):2  (6,7):4  ...

2단계: 크루스칼 알고리즘 실행

단계	간선	비용	선택	누적비용	최대비용
1	(3,2)	1	✅	1	1
2	(6,4)	1	✅	2	1
3	(1,3)	2	✅	4	2
4	(1,6)	2	✅	6	2
5	(2,5)	2	✅	8	2
6	(6,7)	4	✅	12	4

3단계: 결과 계산

MST 총 비용: 12
가장 비싼 간선: 4
답: 12 - 4 = 8

---

왜 이 방법이 정답일까?

🤔 증명

1. MST의 성질: N개 정점을 N-1개 간선으로 최소 비용으로 연결
2. 분할의 조건: 간선 하나 제거 시 정확히 두 개의 연결 컴포넌트 생성
3. 최적성: 가장 비싼 간선을 제거해야 남은 비용이 최소

💡 직관적 이해

마을 전체를 최소 비용으로 연결한 후, 가장 비싼 길 하나만 끊으면 두 마을로 나뉘면서 각 마을 내부는 여전히 연결되어 있습니다.

---

시간복잡도

연산	복잡도	설명
정렬	O(M log M)	간선 정렬
Union-Find	O(M α(N))	α는 거의 상수
전체	O(M log M)	정렬이 지배적

---

구현 시 주의사항

⚠️ 실수하기 쉬운 부분

1. 경로 압축 빼먹지 않기

   def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])  # 이 부분!
    return parent[x]

2. 가장 비싼 간선 추적 놓치지 않기

   max_cost = max(cost, max_cost)  # MST에 추가할 때마다 업데이트

3. sys.stdin.readline 사용하기 (시간 초과 방지)

✅ 핵심 포인트

• MST를 구성하면서 동시에 가장 비싼 간선 추적
• 별도로 MST를 구성한 후 다시 찾을 필요 없음
• O(M log M) 시간에 한 번에 해결

---

마무리

🎯 문제의 핵심

이 문제는 "두 개로 나누기 = 간선 하나 제거하기"라는 그래프 이론의 기본 성질을 이해하고 있는지 묻는 문제입니다.

MST의 성질을 정확히 이해한다면, 복잡해 보이는 문제도 간단한 아이디어 하나로 해결할 수 있습니다.

💡 기억할 점

MST 총 비용 - 가장 비싼 간선 = 두 마을로 분할했을 때 최소 비용