BOJ 5719 거의 최단 경로

시작

https://lotuslee.tistory.com/137 본문을 참고하였습니다.

문제를 읽어보면 한가지 좋은 아이디어를 생각해볼 수 있었는데 구현이 쉽지 않았습니다.

아이디어는 비교적 간단합니다.

1. 다익스트라로 최단 경로를 구합니다.

2. 최단 경로들을 모두 제외 합니다.

3. 다익스트라로 다음 최단 경로를 구합니다.

그림으로 보면 다음과 같습니다.

각 순서는 그림에서 왼쪽부터 1, 2, 3으로 확인해 볼 수 있습니다. 

소스코드를 우선 살펴보겠습니다. 

 

코드 중에 preNodeCollections, ArrayList 를 선언해 두었습니다. 

최소 비용을 가진 경로를 담아두기 위한 목적인데,

거리 값이 갱신 되면 왼쪽에 보이는 1번 경로가 clear 되고 2번 경로가 preNodeCollections에 연결됩니다. 

 

 

결과적으로 같은 값을 가질 수 있는 복수개의 최단 비용의 경로를 모두 담아두는것이 이 문제를 해결하는 가장 큰 힌트입니다.

 

최소 비용의 거리에 포함되는 노드를 preNodeCollections에 저장해 두지만,

사실 이 경로를 파악하기 위해서는 오른쪽의 그림에서 보이는것과 같이 1, 2, 3 중 간선 값의 최소를 구하고 이것이 4에 저장되고

또, 4, 5, 6 중 간선 값의 최소를 구해서 이것이 7에 저장되는 로직으로 구성됩니다.

이렇게 최소 비용 거리를 구하게 되면 처음 최소 비용 거리 외에도 다른 경로지만 최소 비용 거리가 같은 것들이 모두  preNodeCollections에 저장하게 됩니다.

 

그 외 코드

else로 분기되는 시점에서 다익스트라 구현 방법과 똑같은데 

if/else if 의 조건문을 자세히 보시면 최소 비용 경로를 구한 뒤에 이와 똑같은 경로들도 담아두기 위해서 preNodeCollections에 저장합니다. 

 

다익스트라 알고리즘에 대한 실행을 한번 한 후에 최단 거리 비용이 최솟값으로 나올 수 있는 경로에 대해 모두 boolean 값을 true 로 변경합니다. 

결과적으로 두번째 다익스트라에서 preNodeCollections의 역할을 큰 의미가 없습니다.

이미 최단 경로를 구하고 이를 방문 처리 하여 두번째 다익스트라만으로도 거의 최단 경로를 구할 수 있기 때문에 

전체 알고리즘 로직의 다익스트라 ⇢ 방문 표시 ⇢ 다익스트라를 수행하여 해결할 수 있습니다.