도시 분할 계획

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

분류:: 최소 신장 트리 

 

1. 문제 이해 및 해결과정

- 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. => 최소한의비용으로 2개의 신장 트리로 분할하려면 어떻게 하면 될것인지

- 크루스칼 알고리즘으로 최소 신장 트리를 찾고 가장 큰 비용을 가지는 간선을 제거하자 

 

2. 풀이방법

 1. 크루스칼 알고리즘

#도시 분할 계획
#
'''
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4
#출력
8
'''
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())

parent=[0]*(n+1)
edges = []
result=0
for _ in range(m):
    a,b,c=map(int,input().split())
    edges.append((c,a,b)) #비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정

edges.sort()

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


max_cost=0
for edge in edges:
    c,a,b=edge
    #사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result+=c
        max_cost=max(max_cost,c)

result-=max_cost
print(result)

 

3. 오답원인

 

4. 알게된 점