✓

태그:

24. 최단 경로 CLASS 4

두 점을 지나야한다고 해봤자 가능한 경우는 단 2가지입니다!

풀이 비스무리한거 보기

방향이 없는 그래프가 주어졌을 때, 특정한 두 점을 지나는 최단 경로를 찾는 문제입니다. 다익스트라를 사용하여 1번 점으로부터 v₁번 점까지의 최단 거리(이하 [1,v₁]), [1,v₂], [v₁,v₂], [v₁,n], [v₂,n]을 구합니다. 어차피 두 점 v₁와 v₂을 지나는 [1,n]은 [1,v₁][v₁,v₂][v₂,n]와 [1,v₂][v₂,v₁][v₁,n]의 2가지 경우밖에 없기 때문입니다. 따라서 5개의 최단 거리를 모두 구한 후 경로가 존재한다면 둘 중 작은 값, 존재하지 않는다면 -1을 출력하면 됩니다.

저는 일일이 최단거리 구하기 귀찮아서 플로이드-와셜 알고리즘을 사용했습니다. 모든 점 쌍에 대해 최단 거리를 구한 후, [1,v₁][v₁,v₂][v₂,n]와 [1,v₂][v₂,v₁][v₁,n] 중 짧은 것을 고릅니다. 출력하기 전에 [1,n]의 경로가 존재하는지부터 판별하여 존재하지 않는다면 -1, 존재한다면 최단 거리를 출력하는 방식으로 풀었습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-09 22:45:16

---