[백준] No.1185 - 유럽여행 (C++, MST 크루스칼)

문제

 

https://www.acmicpc.net/problem/1185

1185번: 유럽여행

 

풀이

 

solved.ac 난이도: Platium 4

 

간선의 가중치를 알맞게 변경시켜주어야 해결할 수 있는 최소 스패닝 트리(MST) 문제.

 

일단 문제를 읽어보면 MST 문제임을 알리는 힌트를 준다.

N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다.
즉, N-1개의 길만을 남겨야 할 것이다.

 

 

하지만 문제의 힌트를 읽어보면 일반적인 MST와는 다른 경로로 진행한 것이 정답임을 알 수 있다.

민식이가 먼저 4번 나라에 도착한 다음 4-5-4-2-3-2-1-2-4 순서대로 나라를 방문하면 총 176 비용이 드는 것을 알 수 있다.

 

힌트에서 주어진 경로가 가능한 그래프는 다음과 같다.

 

 

하지만 단순한 MST라면 3과 5를 잇는 6 cost의 간선이 있는데 4와 5를 잇는 12 cost의 간선을 MST로 선택할 이유가 없을 것이다.

 

 

이는 길을 지나는 것뿐만 아니라 다른 나라에 도착하면 비용을 지불해야 하기 때문이다.

그렇다면 간선의 가중치를 어떻게 설정해야 할까?

 

트리에서 특정 정점에서 시작하여 모든 정점을 방문 후 다시 시작 점으로 돌아오는 경로를 생각해보자.

힌트의 경로와 같이 4번 정점에서 시작한다면 다음과 같이 모든 간선을 결국 2번씩 지나게 된다.

그렇다면 다른 정점에서 시작하면 어떨까?

1, 2, 3, 5번 정점에서 모두 다른 정점을 한 번씩 방문하고 오는 경로는 결국 위와 동일하다.

즉, 트리에서 시작점에서 다른 점을 방문하고 복귀하는 경우 모든 간선은

결국 진입하는 방향과 진출하는 방향을 한 번씩, 총 두 번 지나게 된다.

 

간선은 두 번씩 지나게 된다면 정점은 어떨까?

어디서 출발하든, 정점은 간선으로 이어진 다른 정점으로 이동(진출) 후 다시 정점으로 복귀(진입)한다.

따라서 정점은 자신의 간선의 개수(차수, degree)만큼 방문된다.

 

만약 u정점에서 v정점으로 이동 후 복귀한다고 가정해보자.

 

진출 시

v로 이동 시, 길의 비용과 v도시의 방문 비용을 내게 된다.

즉, 간선의 cost는 길의 이동 비용 + 도시의 방문 비용이 된다.

 

진입 시

반대로 v에서 u로 복귀하는 경우는 길의 이동 비용 + u도시의 방문 비용을 내야 한다.

결국, u에서 v로 이동 후 다시 v로 복귀하려면 간선을 두 번 지나고, u와 v를 한 번씩 방문하기 때문에

u와 v를 잇는 간선의 가중치(w)는 다음과 같이 표현할 수 있다.

 

w(u, v) = (길의 이동 비용 x 2) + (u도시의 방문 비용) + (v도시의 방문 비용) 

 

따라서 위의 트리의 간선의 가중치는 다음과 같이 표현할 수 있다.

(위의 트리의 그림들에서 1과 2를 잇는 간선의 가중치는 5가 아닌 12로 잘 못 표기하였음을 알립니다.)

 

 

간선의 가중치를 방문하는 두 나라와 그 길의 비용의 합으로 변경하였다면 

변경된 간선들로 크루스칼 MST 알고리즘을 진행하여 최소 스패닝 트리의 간선의 가중치 합을 구할 수 있다.

 

단, 마지막으로 시작 도시는 출발 시 한 번 더 방문 비용을 내야 하므로 가장 작은 비용의 도시를 시작 도시로 설정해 주면 된다.

따라서 문제의 답은 MST 간선의 가중치 합  + 가장 작은 방문 비용이다.

 

 

 

코드