[그래프이론] 어두운 길

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분

1. 문제 설명

- 마을에 설치되어 있는 가로수를 줄여서 비용을 줄이려고 한다. 가로수를 줄였을 때 절약할 수 있는 금액의 최대를 출력하는 문제

2. 접근 방식

- 최소비용으로 모든 노드를 연결하는 문제(크루스칼 알고리즘)

- 추후 간선의 길이가 길어질 것을 대비해 heapq를 활용해서 구해봤다. 

3. 코드

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):
    x = find_parent(parent, a)
    y = find_parent(parent, b)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
        
n, m = map(int, input().split())

import heapq
city = []
for _ in range(m):
    a, b, cost = map(int, input().split())
    heapq.heappush(city, (cost, a , b))
    
parent = list(range(n))
total_cost, result = 0, 0
while city:
    cost, a, b = heapq.heappop(city)
    total_cost += cost
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
print(total_cost - result)

4. 코멘트

- 최소비용으로 모든 노드를 연결하는 문제라는 것은 쉽게 캐치해서 문제를 풀었다. 하지만 모든 노드를 연결했을 때의 비용이 아닌, 기존 비용에서 '얼마를 줄일 수 있는지'를 묻는 문제였다. 그래서 한번에 문제를 풀어내지 못했다.

- 아직까지도 문제를 주의깊게 읽지 못하는 거 같다.