[이코테] 도시 분할 계획 - 이해까지 도와주는 풀이

문제

 

동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느날 원숭이 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다. 

마을 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.

각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다.

마을에는 집이 하나 이상 있어야 한다. 그렇게 마을 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.

그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 없앨 수 있다.

마음의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.

이것을 구하는 프로그램을 작성하시오.

 

입력 조건

 

첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다.

그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

 

 

출력 조건

 

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

 

 

풀이

 

이 문제는 크게 두 단계로 해결할 수 있습니다.

 

첫 번째 단계는 모든 집들을 연결하는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 것이며,

두 번째 단계는 이 트리에서 가장 비용이 큰 길을 하나 제거하여 두 개의 분리된 마을을 만드는 것입니다.

MST를 구하기 위해 Kruskal 알고리즘 또는 Prim 알고리즘을 사용할 수 있습니다. 여기서는 Kruskal 알고리즘을 사용하겠습니다. 

 

Kruskal 알고리즘은 모든 길들을 비용에 따라 오름차순으로 정렬한 다음, 사이클을 형성하지 않는 길을 선택하여 최소 신장 트리를 구성합니다.

구현 단계는 다음과 같습니다.

1. 길들을 유지비 C에 따라 오름차순으로 정렬합니다.

2. 각 집을 자신만의 집합으로 초기화합니다.

3. 정렬된 길들을 차례대로 검토하면서, 두 집이 서로 다른 집합에 속해 있다면 그 길을 선택하고 두 집을 같은 집합으로 합칩니다. 이 과정에서 사이클을 형성하지 않도록 주의합니다.

4. 선택된 길들로 구성된 최소 신장 트리에서 가장 비용이 큰 길을 하나 제거합니다.

5. 남은 길들의 유지비 총합을 계산합니다.

 

 

왜 가장 비용이 큰 길을 하나 제거하면 길이 두개로 나누어질까?

이 방법이 두개의 분리된 마을로 나누는 데 왜 효과적인지 설명하기위해 간단한 예시를 들어보겠습니다.

 

예를 들어, 다음과 같은 마을 구조를 생각해볼 수 있습니다.

 

위 그래프는 주어진 마을의 구조를 나타냅니다. 각 노드(A, B, C, D, E)는 마을의 집을 나타내면, 연결된 간선은 길을 의미합니다.

간선에 표시된 숫자는 해당 길의 유지비를 나타냅니다.

 

이제 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구성하고, 가장 비용이 큰 길을 제거하여 두 개의 분리된 마을을 형성하는 과정을 시각화해보겠습니다.

 

이 때, 각 길의 유지비를 기준으로 오름차순으로 정렬하면 다음과 같습니다: A-B, B-C, C-D, D-E, E-A.

 

이제 Kruskal 알고리즘을 사용하여 MST를 구성합니다. 

이 과정에서 사이클을 형성하지 않는 가장 작은 비용의 길을 차례대로 선택합니다.

 

 

MST

 

1. A-B를 선택합니다 (총 비용: 1).
2. B-C를 선택합니다 (총 비용: 3).
3. C-D를 선택합니다 (총 비용: 6).
4. D-E를 선택합니다 (총 비용: 10).
5. E-A는 선택하지 않습니다, 왜냐하면 이 길을 추가하면 사이클(A-B-C-D-E-A)이 형성되기 때문입니다.

 

이제 MST의 총 비용은 10이며, 마지막에 추가된 간선 D-E의 비용은 4입니다.

이 간선을 제거하면, 다음과 같은 두 개의 분리된 마을이 형성됩니다

 

마을 1: A-B-C
마을 2: D-E

가장 비용이 큰 간선을 제거한 후 남은 길들의 총 유지비는 10 - 4 = 6입니다.

이 예시에서 볼 수 있듯이, 가장 비용이 큰 간선을 제거하는 것은 MST를 두 개의 연결된 부분으로 분할하는 가장 효율적인 방법입니다. 이렇게 함으로써, 각 부분 내에서는 모든 집들이 여전히 서로 연결되어 있으면서, 전체 유지비는 최소화됩니다.

 

소스코드

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)  # a의 루트 노드 찾기
    b = find_parent(parent, b)  # b의 루트 노드 찾기

    if a < b:
        parent[b] = a  # b의 루트를 a로 설정하여 두 집합을 합침
    else:
        parent[a] = b  # a의 루트를 b로 설정하여 두 집합을 합침

n, m = map(int, input().split())  # 정점의 개수(n)와 간선의 개수(m)를 입력 받음
parent = [0] * (n+1)  # 각 정점의 부모 노드를 저장하는 리스트 초기화


edges = []  # 간선 정보를 저장할 리스트
result = 0  # 최소 스패닝 트리의 가중치 합을 저장할 변수


for i in range(n+1):
    parent[i] = i  # 초기에는 각 정점이 자기 자신을 부모로 갖음

for _ in range(m):
    a, b, cost = map(int, input().split())  # 간선 정보 입력 받음
    edges.append((cost, a, b))  # 간선 정보를 가중치(cost)와 함께 리스트에 추가

# 가중치를 기준으로 간선 리스트 정렬
edges.sort()
last = 0  # 최소 스패닝 트리의 가장 큰 가중치 간선을 저장할 변수

# 최소 스패닝 트리 구성
for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):  # a와 b가 다른 집합에 속해 있다면
        union_parent(parent, a, b)  # 두 집합을 합침
        result += cost  # 사이클을 형성하는 간선의 가중치를 더해줌
        last = cost

print(result - last)  # 최소 스패닝 트리의 가중치 합에서 가장 큰 가중치 간선의 가중치를 빼서 출력