[BOJ] 백준 11780 플로이드 2 (Swift)

문제

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

11780번: 플로이드 2

풀이

플로이드워셜 알고리즘으로 풀이할 수 있는 문제입니다.

경로를 확인하기 위해 routes[1][5] = [1, 3, 5]와 같이 3차원 Int 배열을 사용하였습니다.
1에서 5로 가는 루트는 1 -> 3 -> 5 를 나타낸 것입니다.

초기의 버스와 버스 사이의 비용은 임의로 큰 수를 넣어주었고,
A 도시와 B 도시의 비용을 입력받을 때, 비용을 갱신해주었습니다.
다만 주의해야할 점으로는 A에서 B로 가는 경로가 1개라는 법은 없기 때문에, 작은 비용으로 갱신해주어야 합니다.
A에서 B로 가는 루트는 A -> B가 됩니다.

routes[A][B] = [A, B] 가 되겠네요.

그 이후, A에서 K도시를 거쳐서 B도시를 갈 수 있는 모든 비용에 대해 확인을 해서, 최소 비용으로 갱신해주어야 합니다.
최소 비용으로 갱신된다면 A에서 K도시를 거쳐 B로 가는 루트는 A -> K -> B 가 됩니다.
routes[A][B] = routes[A][K] + routes[K][B] 가 될 것인데, K가 중복되므로 둘 중에서 하나의 K를 빼주어야 합니다.

최소 비용을 출력하고, 모든 경로에 대해 출력해줍시다.

소스코드

후기

최소 비용으로 갱신되는 경우에 대해서 경로를 갱신시켜주어야 하는 문제였습니다.