[BOJ] Q1149 도시 분할 계획

[BOJ] Q1647 도시 분할 계획

Question

Language: Python

Difficulty: Gold 4

N개의 집, M개의 도로에 대해서, 2개의 마을로 분할 하고, 마을 내에 있는 길의 유지비 합을 최소화 하고자 한다.

길의 유지비(weight)을 최소화 한다. –> MST, 근데 이때 2개의 마을이 이므로 2개의 MST가 필요하다.

MST 1개를 만드는 것 kruskal algorithm을 이용하면 간단히 해결할 수 있다. 그럼 2개의 MST는 어떻게 구할까 ?? –> MST에서 간선 1개를 제거하면 MST 2개가 생성된다. 또한, 간선 중에서도 weight가 가장 높은 간선을 지우면 최적의 2개의 MST가 생성된다. MST 1개를 만드는 것 kruskal algorithm을 이용하면 간단히 해결할 수 있다. 그럼 2개의 MST는 어떻게 구할까 ?? –> MST에서 간선 1개를 제거하면 MST 2개가 생성된다. 또한, 간선 중에서도 weight가 가장 높은 간선을 지우면 최적의 2개의 MST가 생성된다.

Solution

import heapq

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

def union_parents(parents,x,y):
    pre_x=find_parents_compressed(parents,x)
    pre_y=find_parents_compressed(parents,y)

    if pre_x < pre_y:
        parents[pre_x]=pre_y
    else:
        parents[pre_y]=pre_x

def solution():
    #간선 집합 정렬
    edges.sort(key=lambda x:x[2])
    parents=[0] * (v+1)
    for i in range(1,v+1):
        parents[i]=i

    result=0
    edge_count=0
    max_cost=0
    
    for v1,v2,cost in edges:
        #cycle 여부를 확인하기 위해 disjoint_set을 이용한다.
        if find_parents_compressed(parents,v1) != find_parents_compressed(parents,v2):
            union_parents(parents,v1,v2)
            result+=cost
            max_cost=max(max_cost,cost)
            edge_count+=1
            if edge_count==v-1:
                break
            else:
                continue
    return result-max_cost

if __name__ == "__main__":
    v,e=map(int,input().split())
    edges=[list(map(int,input().split())) for _ in range(e)]

    print(solution())