어두운 길

출처::  University of Ulm Local Contest

분류:: 크루스칼

 

1. 문제 이해 및 해결과정

- 최소한의 비용으로 모든집을 연결해야한다 => 최소 신장 트리문제 - 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 -> 최소 신장 트리 문제 의심해야한다 - 왕래할 수 있다는 것은, 그래프에서 각 노드가 서로 연결되어 있다는 의미와 같기 때문이다 - 크루스칼 알고리즘 - 구하는 것은 절약할 수 있는 최대 금액 이므로 전체 가로등 켜는 비용 - 최소 신장 트리 비용

2. 풀이방법

 1. 크루스칼

#어두운 길
#
import sys
sys.stdin = open("input.txt","r")

n,m=map(int,input().split())
parent=[0]*(n+1)

for i in range(1,n+1):
    parent[i]=i

edges=[]
result=0

for _ in range(m):
    x,y,z=map(int,input().split())
    #비용순으로 정렬
    edges.append((z,x,y))

edges.sort()
total=0 #전체비용
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
        
for edge in edges:
    cost,a,b=edge
    total+=cost
    #사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost
print(total-result)

  

 

3. 오답원인

 

4. 알게된 점

크루스칼 알고리즘

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다

  2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함

  2-2. 사이클이 발생하는 경우 최소 신장 트리에 포함 시키지 않는다

3. 모든 간선에 대해서 2번 과정을 반복한다