BOJ 8236 - Price List 링크
(2023.05.30 기준 D1)

문제

n개의 마을을 잇는 m개의 철도가 있다. 그리고 각 철도의 비용은 a다.
철도로 직접 이어지지 않았으며, 정확하게 최단 거리의 철도 개수가 2개인 두 마을은 비행기를 이용하여 갈 수 있다. 비행기의 비용은 b다.
이 때, k 마을에서 1 ~ n까지의 최단 경로의 비용 출력.

알고리즘

BFS

풀이

먼저 철도로만 이용했을 때에 최단 경로를 생각해보자. 모든 간선의 가중치는 a로 동일하다. 그러므로 BFS를 이용하면 된다.
BFS의 결과는 철도를 이용하는 횟수가 될 것이다. 그렇다면 철도를 두 번 이용하는 것은 비행기를 한 번 이용하는 것과 같다.

그렇다면 각 마을로의 최단 경로의 비용은

dist[i] // 2 * min(a * 2, b) + dist[i] % 2 * a

가 될 것이다.

여기까지는 되게 쉽다.
하지만, 놓치기 쉬운 부분이 있다.

이런 예제에서 5까지의 최단 경로를 생각해보자.
BFS를 돌리면 5까지의 거리는 1이 나온다. 그러면 비용은 1,000이 될 것이다.
하지만 1-2-3-4-5 경로의 비용은? 1 -> 3 (비행기) + 3 -> 5 (비행기) = 2 * b = 2가 나온다.

비행기로 한 번에 갈 수 있는 위치까지의 비용은 b로만 이루어진다.
만약, a가 b보다 크다면 비행기로 한 번에 가는 경로도 고려를 해야 하는 것이다.

그렇다면 이제 비행기로 한 번에 갈 수 있는 위치로의 거리를 BFS로 구해야 한다.
그런데 이 과정에서 한 건너 마을이 인접해 있는지를 따질 때, 분명 이분 탐색을 사용하게 된다. 그런데 이 이분 탐색도 줄여야 한다. 그러므로 인접 그래프에 대해 방문 여부에 따른 최적화를 잘하자.

코드

D3 이상의 문제는 치팅 방지를 위해 코드를 올리지 않겠습니다.