[이코테] 그래프 알고리즘 - 어두운 길

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

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

입력조건

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

출력조건

• 첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력한다.

사고과정

• "임의의 두 집에 대해 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다" 와 "최대한 많은 금액을 절약하고자"라는 키워드를 보고 최소 신장 트리 알고리즘인 크루스칼을 사용할 것이라고 생각했다. 물론 문제에서는 절약할 최대한 많은 금액을 출력하라고 했지만 이는 결국 모든 간선 비용에서 최소 신장 트리비용을 빼주면 되는 아주 살짝의 응용이다.
• 전형적인 크루스칼 알고리즘 문제로 반복해서 알고리즘 코드를 쳐보아서 그런지 쉽게 풀 수 있었다..!

풀이

책과 동일하게 풀이했다.

import sys

# n은 도시, m은 도로 수
n, m = map(int, input().split())
parent = [0] * n
for i in range(n):
    parent[i] = i

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
# 간선 정보 담을 리스트
edges = []
total_cost = 0
for _ in range(m):
    x, y, cost = map(int, input().split())  # x -> y, cost
    total_cost += cost
    edges.append((cost, x, y))
edges.sort()

# 간선 정보 하나씩 처리
result = 0
for i in range(m):
    cost, x, y = edges[i]
    # find 연산 후 부모 노드 같지 X = 사이클 발생 X = union연산 후 최소신장에 포함
    if find_parent(parent, x) != find_parent(parent, y):
        result += cost
        union_parent(parent, x, y)

print(total_cost - result)