[백준 1674번] 도시 분할 계획 문제풀이 (with Python)

< 문제 >

 

 

 

 

< 입출력 >

 

 

 

 

< 풀이 >

모든 마을을 연결시키는 가장 최소의 값에서 가장 큰 유지비가 드는 마을의 연결을 자르면 두 마을이 되면서 최소 유지비를 만들 수 있다.

따라서, 유지 비용이 작은 순으로 정렬하고,  루트 노드가 다를 경우 두 노드를 연결시킨다.

모든 노드를 연결한 후 가장 마지막 유지비용( 가장 큰 유지비용 )을 빼서 결과값을 도출한다. 

 

 

 

 

 

< 코드> 

import sys
input = sys.stdin.readline

def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a,b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


arr = []
result = 0
end_cost = 0
N, M = map(int, input().split())
parent = [i for i in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    arr.append((a, b, c))

arr.sort(key=lambda x : x[2])

for a, b, c in arr:
    if find(a) != find(b):    # 여기서 parent[a] != parent[b] 로 비교하면 안되는 이유가 뭘까??
        union(a, b)
        result += c
        end_cost = c

print(result - end_cost)

 

위 주석의 위치에서 find(a)와 find(b) 를 비교하는 대신 parent[a] 와  parent[b]를 비교하면 안되는 이유가 뭘까??

: parent 배열에는 이미 루트 노드가 저장되어 있는데, 루트 노드를 구하는 함수를 써야하는 이유가 궁금했다.

위의 입력값에서  1 2 3 과 2 5 2 에서 노드 2는 두번 호출되므로 처음의 루트노드와 다를 수 있다.

하지만, 두 노드를 연결할 떄, 이미 find 함수를 이용해 루트 노드를 바꾸어 저장한다. 

생각해보니 만약 노드 5가 두번 호출되는 상황에서,

처음 호출될 때 노드 5의 루트 노드가 3 으로 변경되고,  이후 노드 3의 루트 노드가 1로 변경 된다면, 노드 5의 루트노드도 1로 변경되어야 하기 때문이었다!!!!!