[백준] 1185: 유럽 여행

🔈 문제

민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다.

각 길을 통과하기 위한 비용이 각기 다르고 한 나라를 도착하면 내야할 비용 역시 나라마다 다르게 정해져있다. 민식이는 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 물론 길과 나라는 여러 번 방문할 수 있고, 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 이러한 민식이의 유럽 계획을 도와주자. 

 

📝입력

첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비용 C
i (1 ≤ Ci ≤ 1,000)가 입력된다. 다음 P개의 줄에는 P개의 길에 대한 정보를 의미하는 세 정수 Sj, Ej, Lj가 입력되는데 이는 Sj번째 나라와 Ej번째 나라 사이를 연결짓는 길을 통과하기 위해서는 Lj 비용이 든다는 의미이다. (Sj ≠ E j, 0 ≤ Lj ≤1,000)

 

📑출력

첫 줄에 민식이가 유럽여행을 마치기 위한 최소비용을 출력한다.

 

📚 문제 풀이

 

문제의 요구 사항을 바탕으로 경로를 정리해보면 우선 n-1 개의 간선으로 구성된 트리를 만들어야 한다. 

시작점을 정하고 모든 노드를 방문한 뒤에 다시 시작점으로 돌아와야 한다는 조건이 있다. 이 조건이 있기에 모든 간선을 정확히 두번씩 지나간 다는 것을 확인할 수 있다.

n-1개의 간선으로 구성된 트리기에 a -> b의 경로는 유일하다. 반대로 b -> a의 경로도 유일한데 a -> b 를 뒤집은 것과 같다. 

 

기본적인 MST 를 구성할 때에는 간선의 가중치를 기준으로 정렬한다. 하지만 이 문제에서는 일단 트리를 구성하면 해당 트리에 포함되는 간선은 무조건 두번만 사용되기에 이동시에 사용되는 비용은 (트리를 구성하고 있는 간선) * 2 를 하여 구할 수 있다. 때문에 단순히 간선만 가지고 정렬하기엔 무언가 부족하다. 

 

그럼 이제 노드에 초점을 둬보자. 노드 방문 횟수는 해당 노드의 연결되어 있는 간선의 갯수에 영향을 받는다. a 라는 노드에 총 4개의 간선이 있다면 a 노드는 4번 방문한다. 그리고 시작점 노드는 추가로 한번 더 방문하게 된다. 그렇다면 시작점은 각 나라의 방문 비용중 최소인 곳으로 잡는것이 최소비용이 된다.

 

유럽 여행에 드는 비용은 n-1 개의 간선으로 이루어진 트리에서, (간선의 총합)*2 + (방문 비용 * 노드의 연결된 간선 갯수) + 최소비용 이 된다. 

 

이제는 트리를 어떻게 구성하는지가 관건이다. 

간선을 지나갈때 그 간선의 비용만 추가되는 것이 아니라 간선이 이어주고 있는 노드의 방문 비용도 추가가 된다. 이 방문비용까지 추가해서 정렬를 해주면 된다!!! 

 

 

💻 코드

# 간선은 정확이 두번 사용
# 정점은 두번이상
import sys, heapq
input = sys.stdin.readline
 
def find(parent:list[int], x:int) -> int:
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]
 
def union(parent:list[int], a:int, b:int) -> None:
    a = find(parent, a)
    b = find(parent, b)
 
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
def solve():
    n,p = map(int,input().split())
    parent = [i for i in range(n+1)]
    cost = [0] + [int(input()) for _ in range(n)]
    edges = [list(map(int,input().split())) for _ in range(p)]
    edges.sort(key=lambda x:2*x[2]+cost[x[0]]+cost[x[1]])
    ans = min(cost[1:])
    mst = 0
 
    for u,v,w in edges:
        if find(parent, u) != find(parent, v):
            union(parent, u, v)
            ans += 2*w+cost[u]+cost[v]
            mst += 1
            if mst == n-1: break
    return ans
if __name__ == "__main__":
    print(solve())

 

🍭 시행착오

 

열심히 최적화 하여 

 

 

파이썬 유저중 1등(20230824 기준)이다! 

 

틀렸던 이유는 정렬할 때 (간선 비용 + a의 방문 비용 + b의 방문 비용) 이렇게 정렬했기 때문이다. 문제의 조건중 간선의 비용이 0 이 될 수 있다는 조건이 있다. 간선은 무조건 두번 사용되니 (간선 비용*2 + a의 방문 비용 + b의 방문 비용) 이렇게 정렬하는 것이 맞다. 

 

🔗 문제링크 1185 유럽여행

1185번: 유럽여행