백준(BOJ) 1185 유럽여행(Python)

문제 내용

 

최소 신장 트리 문제.

크루스칼 알고리즘으로 해결했다.

입력받은 간선의 가중치를 수정해서 문제를 해결했는데, 가중치를 (원래 가중치)*2+(양 노드의 방문 비용)으로 수정했다.

모든 길을 제거한 상태가 트리이므로, 어떤 한 노드에서 출발해 다른 모든 노드를 방문하고 다시 원래 노드로 돌아오기 위해서는 모든 간선을 2번씩 거쳐야 하기 때문이다.

그 과정에서 양 노드의 방문 비용도 발생하기 때문에 처음부터 간선의 가중치를 그 간선을 왕복할 때의 비용으로 수정해서 문제를 풀 수 있었다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

v,e=map(int,input().split())
L=[]
C=[0 for i in range(v+1)]
cycle=[i for i in range(v+1)]
ans=0
n=0
k=1001
for i in range(1,v+1):
    C[i]=int(input())
    k=min(C[i],k)
for i in range(e):
    a,b,c=map(int,input().split())
    heapq.heappush(L,[2*c+C[a]+C[b],min(a,b),max(a,b)])
    
def find(u):
    if u!=cycle[u]:
        cycle[u]=find(cycle[u])
    return cycle[u]

def union(u,v):
    u=find(u)
    v=find(v)
    cycle[v]=cycle[u]

while n<v-1:
    c,a,b=heapq.heappop(L)
    if find(a)!=find(b):
        ans+=c
        union(a,b)
        n+=1
print(ans+k)

 

아이디어를 떠올리는 것은 어렵지 않았는데, 처음에 문제를 제대로 안 읽어서 트리가 아닌 경우도 고려한다고 시간이 조금 걸렸다.

문제를 제대로 읽자.