[이코테] 그래프 알고리즘 - 도시 분할 계획

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

 

---

문제설명

해당 문제는 백준 온라인 저지에서 제공하는 문제이다. 하단의 링크를 참조하자.

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

사고과정

• 문제에서 'N개의 집, M개의 길로 연결' , '어느 방향으로 갈 수 있다 = 무방향', '길을 유지하는 데 드는 비용 = 간선 비용', '두 집 사이에 항상 경로가 존재하게 하면서 다른 길을 없애는 것 = 최소 신장 트리' 키워드를 뽑아낼 수 있었다. 그런데 문제의 2번째 문단의 조건까지 포함해서 구해야 하는건지 읽다가 의문이 들었다. 이 부분을 명확히 해결하지 못하고 문제 풀이를 냈지만 시간초과 판정을 받았다.
• 결국 2번째 문단 조건도 충족시켜야 하는 문제였는데, 결국 전체 그래프에서 최소 신장 트리 2개를 구하는 문제였다. 크루스칼 알고리즘을 사용하는 코드는 잘 구현했는데, 핵심 포인트인 최소 신장 트리 2개를 구하는 데 드는 최소 비용은 최초에 구한 최소 신장 트리 중에 가장 간선 비용이 큰 간선을 제거해주면 되는 것을 놓쳤다...

풀이(스스로 못 푼 풀이)

import sys

n, m = map(int, input().split())
parent = [0] * (n+1)
for i in range(1, n+1):
    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 = []
result = 0
for _ in range(m):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

edges.sort()
result = 0
last = 0

for i in range(m):
    cost, a, b = edges[i]
    # find 연산 후 부모노드 같은지 살피기
    if find_parent(parent, a) != find_parent(parent, b): # 부모노드 다르면 사이클 발생 X -> union 연산 수행 -> 최소 신장트리에 포함
        union_parent(parent, a, b)
        result += cost
        last = cost # 가장 마지막 loop순서가 cost가 최소 신장트리에 포함시키는 간선들 중 가장 큰 비용이 됨

print(result - last)