동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계힉을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.
- 그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C(1 <= C <= 1,000)라는 뜻이다.
출력 조건
- 첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다.
# 리스트를 정렬하기 위한 퀵정렬 코드
def quick_sort(a, start, end):
if end - start <= 0:
return
pivot = a[start]
i = start + 1
j = end
while True:
while a[i] < pivot and i <= end: i += 1
while a[j] > pivot and j >= start :
j -= 1
if i < j:
a[i], a[j] = a[j], a[i]
else:
a[j], a[start] = a[start], a[j]
break
quick_sort(a, start, j - 1)
quick_sort(a, j + 1, end)
# 특정 집이 속한 집합을 찾기
def find_parent(parent, a):
if parent[a] != a:
parent[a] = find_parent(parent, parent[a])
return parent[a]
# 두 집이 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a > b:
parent[a] = b
elif b > a:
parent[b] = a
# n, m을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 자신의 부모 노드를 자신으로 초기화
parent = [0] * (n + 1)
for i in range(n + 1):
parent[i] = i
# 모든 길 정보를 담을 리스트(유지비, 집1, 집2)
roads = []
for _ in range(m):
a, b, c = map(int, input().split())
roads.append((c, a, b))
# 유지비 기준으로 오름차순으로 정렬
quick_sort(roads, 0, m - 1)
answer = 0
for road in roads:
cost, a, b = road
# 한 마을을 구성하는데 cycle이 생기지 않으면
if find_parent(parent, a) != find_parent(parent, b):
# 두 집이 속한 집합들을 합친다.
union_parent(parent, a, b)
max_cost = cost
answer += cost
# 마을 2개로 분리하기 위해 유지비가 가장 많이 드는 길 없애기
answer -= max_cost
print(answer)
리스트에 내장되어있는 정렬 메소드를 사용하는데 익숙해져서 막상 퀵정렬 코드를 짜려니 기억이 잘 안나서 한 번 직접 정렬 코드를 작성해서 문제를 풀어보았다.
가끔 라이브러리에 이미 구현된 자료구조나 알고리즘과 관련된 코드들을 한번씩 작성해보는 것이 좋을 것 같다.