[UULC] 어두운 길

문제

한 마을은 N개의 집과 M개듸 도로로 구성되어 있습니다. 각 집은 0번부터 N - 1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.

 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요.

 

입력 조건

- 첫째 줄에 집의 수 N(1 $\le$ N $\le$ 200,000)과 도로의 수 M(N - 1 $\le$ M $\le$ 200,000)이 주어집니다.

- 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분합니다. (0 $\le$ X, Y $\lt$ N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미입니다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 $2^{31}$보다 작습니다.

 

출력 조건

- 첫째 줄에 일부 가로등을 비활성화시켜 절약할 수 있는 최대 금액을 출력합니다.

 

입력 예시

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

 

출력 예시

51

---

 길은 양끝의 마을에서 오갈 수 있으며, 가장 적은 비용으로 모든 마을을 연결하고자 합니다. 즉, 무향 그래프의 최소 신장 트리를 구하는 문제로 바꿔서 생각할 수 있습니다. 최소 신장트리를 구하는 크루스칼 알고리즘의 시간복잡도는 O(ElogE)입니다. 간선의 개수는 최악의 경우 200,001개이므로 약 100만 번의 연산만으로 충분히 해결할 수 있습니다.

크루스칼 알고리즘: https://jcy1996.tistory.com/35?category=960192 

크루스칼 알고리즘(Kruskal Algorithm)

 단, 절약할 수 있는 최대 금액을 출력하는 문제이므로, 모든 간선의 총합을 구한 뒤 최소 신장 트리의 비용합을 제외하면 정답을 구할 수 있습니다.

 소스코드는 다음과 같습니다.

n, m = list(map(int, input().split()))

graph = []
for _ in range(m):
	x, y, z = list(map(int, input().split()))
	graph.append((z, x, y))
graph.sort()
    
parent = [i for i in range(n)]

def find_parent(parent, x):
    if x != parent[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
        
total_dist = 0
min_dist = 0
for z, x, y in graph:
    total_dist +=  z
    if find_parent(parent, x) != find_parent(parent, y):
        union_parent(parent, x, y)
        min_dist += z

print(total_dist - min_dist)

 일반적인 크루스칼 알고리즘의 구현방식을 따르고 있습니다. 다만 코드의 효율성을 위해서 마지막 반복문에서 전체 비용의 합과 최소 신장트리의 비용합을 모두 구하게 했습니다. 이후 두 값의 차이를 구하면 정답을 도출할 수 있습니다.