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

1. 문제상황

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

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

 

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

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

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

 

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

---

2. 고민해본 내용

기존에 알고리즘 문제를 풀 때 

보통은 그래프의 방향성이 있고잘 이으면 모든 각각의 간선들이 출발지 > 목적지로 동일한 방향성을 가지기 때문에 고려하지 못했다.

 

하지만 우리는 데이터를 Tmap Api를 이용해 구축했고

혹시몰라 이 데이터는 양방향 그래프로 넣었지만 실제 도로는 방향성을 가지고 있어 문제가 생겼다.

 

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

A에서 D로 가는 그래프가 최단경로라고 생각하고 코드를 작성했지만,

실제로 그래프의 방향성이 잘못된 경우가 생길 수 있다.

---

3. 해결 방안

목적지로부터 역방향으로 간선들을 추적할 때

가장 마지막으로 방문했던 정점과 다음  간선의 시작점과 끝 점중 어떤 점과 연결되어있는지 판단한 뒤

해당 간선 데이터를 정방향으로 쓸 지 역방향으로 쓸 지 고려해 코드를 작성했다.

Point prevPoint = new Point(start.getX(), start.getY());
pointList.add(prevPoint);
pointSet.add(prevPoint);

for (TmapRoad tmapRoad : tmapRoadList) {
    pathTotalDistance += tmapRoad.getTotalDistance();
    List<Point> tmapPointList = tmapRoad.getGeometry().getCoordinates();
    Point tmapStartPoint = tmapPointList.get(0);
    Point tmapLastPoint = tmapPointList.get(tmapPointList.size() - 1);
    if (tmapStartPoint.getY() == prevPoint.getY() && tmapStartPoint.getX() == prevPoint.getX()) { 
    // 정방향일경우
        for (org.springframework.data.geo.Point curPoint : tmapPointList) {
            if (pointSet.add(curPoint)) pointList.add(curPoint);
            prevPoint = curPoint;
        }
    } else {
        for (int i = tmapPointList.size() - 1; i >= 0; i--) {
            org.springframework.data.geo.Point curPoint = tmapPointList.get(i);
            if (pointSet.add(curPoint)) pointList.add(curPoint);
            prevPoint = curPoint;
        }
    }
}

---

4. 느낀점

논리적으로 검증하는 과정이 어려웠지만 꽤나 재밌었다