13168. 내일로 여행#

관찰#

문제에서 요구하는 것은 다음 두 가지입니다.

1. \( M \)개의 도시를 순회하는 최소 비용을 구해야 한다.
2. 내일로 티켓을 구매하면 비용이 \( R \)원만큼 들고,
   특정 운송 수단의 간선 비용이 할인된다.

각 간선이 운송 수단 종류, 출발지, 도착지, 비용으로 주어지므로
도시 간 최단 이동 비용을 구한 뒤, 내일로 티켓을 쓰는 경우 / 쓰지 않는 경우의 총 비용을 비교하면 된다.

대표적인 최단 거리 알고리즘으로는

• 한 정점에서 모든 정점까지의 최단 거리를 구하는 다익스트라
• 모든 정점 쌍 사이의 최단 거리를 한 번에 구하는 플로이드–워셜

이 있고, 이 문제에서는 모든 도시 쌍의 최단 비용이 필요하므로 플로이드–워셜을 택했다.

구체적으로는

• “티켓을 사용하지 않은 경우”의 최단 거리 테이블
• “티켓을 사용한 경우(할인 적용)”의 최단 거리 테이블

을 각각 플로이드–워셜로 구한 뒤,
각 \( M \)개의 도시 순서에 대해 두 테이블에서 비용을 합산하고
티켓 값 \( R \)까지 고려해 더 작은 쪽을 선택하면 된다.

시간 복잡도#

V: 정점(도시) 개수, E: 간선(노선) 개수

• 다익스트라 (우선순위 큐 사용): \( O\bigl((V + E)\log V\bigr) \)

• 플로이드–워셜: \( O(V^3) \)

이 문제의 조건은, \( V \le 100 \), \( E \le 10\,000 \), \( M \le 200 \) 이다.

플로이드–워셜은 \( 2 \cdot O(100^3) = 2 \cdot 10^6 \) 수준의 연산으로 충분히 감당 가능하고,
한 번만 돌면 모든 도시 쌍에 대한 최단 거리를 바로 사용할 수 있다.

반면 다익스트라는 한 출발 도시에서만 최단 거리를 구할 수 있으므로,
각 여행 시작 도시마다 다시 돌려야 하고,
내일로 티켓 사용/미사용 두 경우를 나누면 최대 약 \( 2 \cdot M \)번 반복이 필요하다.

이를 대략 계산하면

으로, 마찬가지로 충분히 가능하긴 하지만 플로이드-워셜이 훨씬 더 빠르다.

따라서, 이 문제에서는

• 제한된 \( V \)
• 모든 도시 쌍 간 최단 비용이 필요한 점
• 티켓 유무 두 가지 케이스를 모두 다뤄야 하는 점

을 고려했을 때, 두 번의 \( O(V^3) \)로 모든 정보를 준비할 수 있는 플로이드–워셜이 더 적합하다.

코드#

Github