[백준 5719 C++] 거의 최단 경로

오늘은 백준 5719번 강의실 배정 문제에 대해 다뤄볼 예정이다.

강의실 배정 문제 링크 (백준 5719번 문제): https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

문제 설명 

백준 5719번 거의 최단 경로 문제는 최단 경로가 아닌 경로들 중 최단 거리를 구하는 문제이다. 즉, 최단 거리가 같은 경로를 제외하고 두 번째로 짧은 최단 거리를 구하는 문제이다. 

 

문제 풀이 

백준 5719번 거의 최단 경로 문제를 해결하기 위해서는 다익스트라 알고리즘(시작 노드에서 특정 노드까지의 최단 거리를 구하는 알고리즘)을 사용해야 한다는 것은 쉽게 알 수 있다. 

 

그럼, 거의 최단 경로를 어떻게 구하면 될까? 

우선, 첫 번째로, 다익스트라 알고리즘을 통해 최단 거리를 구해준다. 

두 번째로, 최단 거리에 해당되는 Path를 삭제해준다. 

세 번째로, 다시 다익스트라 알고리즘을 통해 최단 거리를 구해준다. 

 

단, 여기서 주목해야 할 부분은 최단 거리에 해당 되는 Path를 삭제하는 부분이다. 

처음 구현 했을 때, 실수했던 부분은 최단 거리에 해당되는 Path를 0으로 만들어 줌으로 Path를 삭제했다고 생각하고 풀었다. 

즉, 다익스트라 알고리즘을 실행하는 과정에서, 최단 거리로 가는 Path를 저장한 다음, 목적지(destination)에서 역방향으로 Path에 0으로 만들어주었다. 이때, 최단 거리로 가기 위한 중간 Path에서 Path를 한 번 밖에 지우지 않았던 것이다. 

 

0 -> 1 - > 3 -> 4 

0 -> 2 -> 3 -> 4 

 

*주의할 점*

두 경로의 최단 거리가 같다고 할 때, 3 -> 4으로 가는 Path를 0으로 만들어주고, 1 -> 3로 가는 Path를 0으로 만들어주고, 0 -> 1로 가는 Path를 0으로 만들어주고, 다시 다익스트라를 돌렸더니, 0 -> 2 -> 3 -> 4 경로에서 3 -> 4의 Path가 0이 되어 최단 경로를 찾지 못하는 상황이 벌어졌었다. 

 

*핵심 포인트*

이러한 실수로 인해, 여러 번 틀렸고, 이를 해결하기 위해, 목적지(destination)에서 BFS(Breadth-First-Search) 알고리즘을 사용하여 최단 거리에 해당되는 경로를 모두 0으로 만들어주었다. 

 

이와 같은 방식으로 접근한 코드는 아래와 같다.