[백준 1504 C++] 특정한 최단 경로

오늘은 백준(BOJ) 1504번 파티 문제에 대해 다뤄보겠습니다. 

파티 문제 링크 (백준(BOJ) 1504번 문제): https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

문제 설명

백준 1504번 특정한 최단 경로 문제는 1번 정점에서 N번 정점까지 도달하는데 V1과 V2를 무조건 거쳐서 N번 정점에 도달해야하는 문제이다. 

문제 풀이

백준 1504번 특정한 최단 경로 문제는 최단 경로를 구하는 문제이므로, 다익스트라 알고리즘(Dijsktra Algorithm)을 사용하여 해결할 수 있다. 

 

우선, 1번 정점에서 N번 정점에 도달할 수 있는 방법은 아래와 같이 2가지가 존재한다. 

첫 번째, 1 -> V1 -> V2 -> N 

두 번째, 1 -> V2 -> V1 -> N

 

이렇게 보면, 단순한 다익스트라 알고리즘이라고 생각하여 쉬워 보일 수 있지만 정답 비율이 24%로 낮은 이유가 있다. 

문제를 풀면서 고생했던 부분은 단순히 Dijsktra(1, V1) + Dijsktra(V1, V2) + Dijsktra(V2, N) 이런 방식으로 풀게 되면, 셋 중에 하나라도 INF 값을 반환하는 경우 Integer Overflow가 발생하여 세 개의 합을 구했을 때 음수 값이 나오는 것이었다. 

 

그래서, 최단 경로를 구할 때 각 케이스들을 나눠서 생각해주어야한다. 

1. V1 -> V2 거리와 V2 -> V1 거리는 동일하므로 다익스트라를 한 번만 사용하면 된다. 

2. 이후, 1 -> V1 와 1 -> V2 거리를 각각 다익스트라를 통해 최단 거리를 구해준다. 

3. 이때, 구한 값들 중 INF 값이 있는지 확인해준다. 만일 있다면, -1 을 출력 

4. INF 값이 없다면, V1 -> N 과 V2 -> N 거리를 각각 다익스트라로 구해준다. 

5. 4번에서 구한 거리 값 또한 INF 값이 있는지 확인해주면서 각 케이스 별로 값을 구해주면 된다. 

 

이를 코드로 나타내면 아래와 같이 구현할 수 있다.