[BOJ] 백준 1504 특정한 최단 경로 (Swift)

문제

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

1504번: 특정한 최단 경로

풀이

다익스트라 알고리즘을 활용하여 풀 수 있는 문제입니다.
다익스트라 알고리즘으로 특정 노드에서 어느 노드까지의 최단 거리를 알 수 있습니다.

v1과 v2를 무조건 지나야 한다면, 경로는 2개가 나올 것 입니다.

1. start -> v1 -> v2 -> N
2. start -> v2 -> v1 -> N

이 두가지 경로 중 최소 값을 출력해 주면 됩니다.

먼저 start에서 다익스트라 알고리즘을 실행하여 v1까지의 거리와 v2까지의 거리를 구할 수 있습니다.
v1에서 다익스트라 알고리즘을 실행하여 v2까지의 거리와 n까지의 거리를 구할 수 있습니다.
v2에서 다익스트라 알고리즘을 실행하여 v1까지의 거리와 n까지의 거리를 구해 위에서 구한 거리를 합쳐줍시다.

두 거리중 최소 값을 구해주고, 최소 값이 INF 이상이라면 경로가 없는 것으로 판단하면 되므로, -1을 출력해 줍시다.

소스코드

후기

다익스트라 알고리즘을 활용해야 하는 문제였습니다.
다익스트라 어렵네여..