[백준 1185번] 유럽여행 (Python3)

import sys
input = sys.stdin.readline
from heapq import *

def findparent(x):
  if parent[x]!=x:
    parent[x] = findparent(parent[x])
  return parent[x]

N,M = map(int,input().split())
cost = [1e6]+[int(input()) for i in range(N)]

hq = []; parent = [i for i in range(N+1)]
for _ in range(M):
  a,b,c = map(int,input().split())
  heappush(hq,(c*2+cost[a]+cost[b],a,b))

result = 0
while hq:
  c,a,b = heappop(hq)
  if findparent(a)==findparent(b):
    continue
  parent[parent[a]] = parent[b]
  result += c
print(result+min(cost))

간단한 최소 스패닝 트리(MST) 응용문제

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

 

일단 문제에서 N-1개의 길을 남겨야 한다고 힌트를 줬기 때문에 한결 쉽게 해결할 수 있었다. N-1개의 길로 잇는 최단거리는 곧 MST 문제일 확률이 높음을 의미하기 때문이다.

 

중요한 포인트는 간선의 가중치를 어떻게 설정하는지이다. 예를 들어서 현재 a에 있고, b로 연결하고 싶다고 했을때, a에서 b로 방문하고 돌아오기 위해 필요한 비용은 (a>>b비용 + b비용 + b>>a비용 + a비용) 이라고 생각할 수 있다.

따라서 간선의 가중치를 위와 같이 설정한 뒤, 크루스칼 알고리즘으로 해결하면 된다.

 

시작지점의 비용은 어떻게 처리되는지가 문제에서 약간 애매했는데, 예제를 돌려보니 시작지점의 비용은 시작할때와 끝날때 모두 적용된다는 것을 알게되었다. 따라서 MST 연결비용 + 시작지점 비용의 최솟값이 곧 정답이다.

 

 

오늘의 교훈) N-1개의 간선이 존재한다는 특수한 상황을 잘 이용하자.