1185번: 유럽여행
첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비
www.acmicpc.net
전체 나라 개수가 N개이고, 이어져 있는 길이 N-1개 일 때,
최소 비용으로 어느 시작 나라 하나를 정해서 모든 나라를 다 방문한 후 다시 시작 나라로 돌아오기 위해서는 나라는 2*N-1개를 방문하고, 길은 2*(N-1)번을 지나야 한다.
따라서, 각 길의 비용은 이어져 있는 두 나라의 비용 + 길의 비용*2 로 정하면 된다.
예를 들어, 1번과 2번 나라 사이의 길의 비용은
1번 나라의 비용(10) + 2번 나라의 비용(10) + 원래 길의 비용(5)*2 = 30 이 된다.
그 다음, 새로 구한 간선의 가중치를 이용하여 최소 신장 트리(MST)를 구한다.
본인은 이번 문제에서 프림(Prim) 알고리즘을 이용하여 최소 신장 트리를 구하였다.(프림 알고리즘의 경우, 아래 포스팅을 참고)
https://lotuslee.tistory.com/46?category=973233
MST(Minimum Spanning Tree) - 1. 프림 알고리즘
신장 트리(Spanning Tree) : 모든 정점이 간선으로 연결되어 있으면서 사이클이 없는 그래프 예를 들어, 다음과 같은 그래프가 있다고 하자. 위 그래프에서 가능한 신장 트리는 아래와 같다. 1번부터
lotuslee.tistory.com
최소 신장 트리를 구한 결과는 아래 그림과 같다.
최소 신장 트리의 모든 간선의 합을 구하면 30 + 40 + 40 + 60 = 170 이다.
여기서 시작 나라의 비용을 더해줘야 한다.
최소비용을 유지하기 위해서는 5개의 나라들 중에서 비용이 가장 적은 나라를 시작 나라로 정해야 한다.
예제에서 가장 비용이 적은 나라는 5번 나라이다. (비용 = 6)
따라서 최종적으로 드는 최소 비용은 170 + 6 = 176 이 된다.
정답 코드 :
'BOJ' 카테고리의 다른 글
| [백준 1834번] 나머지와 몫이 같은 수(C언어) (1) | 2024.03.22 |
|---|---|
| [백준 25501번] 재귀의 귀재 (0) | 2023.04.08 |
| [백준 14442번] 벽 부수고 이동하기 2 (java) (0) | 2021.06.04 |
| [백준 2206번] 벽 부수고 이동하기 (java) (0) | 2021.06.04 |
| [백준 2550번] 전구 ( java) (0) | 2021.06.02 |