[백준-1185] 유럽여행

박제구·2021년 4월 16일

Algorithm

목록 보기

2/3

https://www.acmicpc.net/problem/1185 👈 문제 확인

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	428	249	196	57.143%

문제

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

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

입력

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

출력

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

문제 풀이

MST (최소 스패닝 트리) 알고리즘 으로 해결할 수 있다.

우선 문제에서 주어진 모든 도시를 최소 한번 이상 방문, 최소 비용, 여러번 방문 가능, 시작 나라 = 마지막 나라를 보았을 때 가중치 값을 그대로 사용한 일반 MST를 만드는 방법을 선택할 수 없다. 왜냐하면, 각 도시는 최소 두번이상 방문해야 해서 돌아오는 길까지 고려해야 하기 때문이다.

그렇다면 어떻게 연결할 그래프와 값을 설정할 수 있을까?

위 처럼 3의 값을 가진 A도시, 4의 값을 가진 B도시, A-B를 연결하는 6의 간선이 있다고 해보자,
A에서 출발하던 B에서 출발하던 결국 간선의 cost는 두번사용되고 두개의 도시를 지나치기 때문에
MST를 만드는 그래프의 distance를 A의 값+B의 값+(cost*2) 로 설정할 수 있다.
즉, (3+4+(6*2))인 19의 값을 가지고 A-B를 연결하는 가중치를 정해야 한다.

가중치를 최솟값 부터 진행하며 Union-find 알고리즘을 적용하여 노드간의 연결유무를 판단하고 모든 노드의 연결이 완성되면 마지막으로 시작점(노드중 최소 비용)을 더해주고 종료한다.

Python3 코드

import sys


def get_parent(parent, x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = get_parent(parent, a)
    b = get_parent(parent, b)
    if a != b:
        parent[b] = a


N, P = map(int, sys.stdin.readline().split())

country = []

for i in range(N+1):
    country.append(i)

country_cost = [2e9] * (N+1)

for i in range(1, N+1):
    country_cost[i] = int(sys.stdin.readline())

graphs = []

for _ in range(P):
    graphs.append(list(map(int, sys.stdin.readline().split())))

for i in range(len(graphs)):
    A, B, dist = graphs[i]
    graphs[i][2] = country_cost[A]+country_cost[B]+2*dist # A노드에서 B노드사이 간선가중치 
    
graph = sorted(graphs, key=lambda x: x[2]) # cost가 적은 순서로 소팅

idx = 0
answer = 0
count = 0
while count < N-1: # 모두 연결되면 종료
    A, B, dist = graph[idx]
    if get_parent(country, A) == get_parent(country, B):
        idx += 1
        continue

    union_parent(country, min(A, B), max(A, B))
    answer += dist
    count += 1
    idx += 1

print(answer + min(country_cost)) # 마지막에 시작점을 더해준다.