[python] 백준 1647 도시 분할 계획

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

1647번: 도시 분할 계획

 

문제 해결

• 조금 고민하면 한 번 노드를 다 이은 후 가장 긴 길이를 빼면 되지 않을까? 싶은 생각을 할 수 있다.
• 하지만 이 때 가장 긴 길이가 짧아서 나눌 때 최소 길이가 되지 않을 수 있지 않나? 생각을 하게 되었다.
• 하지만 정렬(sort)를 이용하여 가장 유지비용이 짧은 두 노드부터 이어가며 모든 노드를 다 이은 다음 가장 나중에 이은 노드를 뺀다면 최소 길이로 이었다는 것을 설명할 수 있다. (각 노드를 가장 싸게 이었으므로)
• 이 때 노드를 연결하는 방법은 최소 스패닝 트리로 크루스칼 알고리즘을 쓰면 된다(유니온 파인드)
• 그러면 노드를 한붓그리기가 아닌 최소 비용의 길을 만들어가며 노드를 연결할 수 있다.

 

CODE

import sys
input = sys.stdin.readline


def find(x):
    if parents[x] != x:
        return find(parents[x])
    return x

def union_find(x,y):
    x = find(x)
    y = find(y)
    if x>y:
        parents[x] = parents[y]
    else:
        parents[y] = parents[x]

def solve():
    global answer
    last_c = 0
    for i in range(m):
        a, b, c = graph[i]
        if find(a) != find(b):
            union_find(a,b)
            answer += c
            last_c = c
    answer -= last_c

if __name__ == "__main__":
    n, m = map(int, input().split())
    graph = [tuple(map(int, input().split())) for _ in range(m)]
    graph = sorted(graph, key=lambda x: x[2])

    parents = [i for i in range(n+1)]
    answer = 0
    solve()
    print(answer)