[Trouble Shooting] 경로가 제대로 나오지 않는 문제 - 1

1. 문제상황

DB를 구축하고 가중치 식 까지 만든 뒤 잘 나오는 JSON을 보고 안심하고 있었지만,

앱에서 직접 경로를 그려보니 위와 같은 문제가 있었다.

 

문제는 크게 두 가지가 있었는데

1. 가중치가 동일할 수가 있다.

2. 도로로 제공되는 그래프의 방향성이 2가지였다.(목적지로 가는 그래프, 출발지로 가는 그래프)

 

이 글에서는 1번 내용에 대해 작성하겠다

---

2. 고민해본 내용

일반적인 상황에서는 나오지 않는 문제이고,

기존에 알고리즘 문제를 풀 때 이런 케이스는 없었기 때문에 고려를 안하고 있었다.

 

하지만 출발점과 목적지가 있을 때 가중치가 완벽히 동일한 경로가 나올 수 있고,

이 경우 경로를 그리는데 문제가 생길 수 있다.

 

예를들면 아래와 같은 문제가 생긴다.

A에서 D로 가기 위한  최소비용은 15이고, 그 길은 A > B > D, A > C > D로 2가지이다.

이를 앱에서 다익스트라 > 역방향 BFS를 이용해 그리게되면 아래와 같은 이상한 결과값이 나오게 된다.

 

---

3. 해결 방안

다음 점을 방문할 때 어떤 점에서 왔는지를 기록하는 배열을 하나 추가해서 해결했다.

arr[B] = A

arr[C] = A

arr[D] = B

arr[D] = C

순서대로 저장되고, 결국 arr[B] = A, arr[C] = A, arr[D] = C가 저장된다.

이후 목적지에서 역방향으로 출발지가 나올 때 까지 추척한다.

arr[D] = C > arr[C] = A > arr[A] = A

즉 하나의 최단 경로는 D > C > A 순으로 왔다는 것을 알 수 있다

---

4. 느낀점

처음 경로 추척은 BFS 알고리즘에서 사용해봤는데, 이를 다익스트라에서도 적용해보고 동작하는것을 확인하니 흥미로웠다