느리게 가는 내비게이션

얼마전에 티맵에서 느리게 가는 네비게이션이 나왔다는 뉴스를 봤다. 

 

“주변 경치 감상하면 천천히”…느리게 가는 내비게이션 출시

보통 내비게이션하면 최단 거리를 구하고, 최단 거리 알고리즘 중에 가장 유명한 것은 다익스트라 알고리즘이다.

다익스트라 알고리즘은 그리디알고리즘으로 그래프의 노드 탐색할 때 BFS를 이용한다. 

 

다익스트라 알고리즘은 가중치가 음수인 경우 처리할 수 없어다. 왜냐면 다익스트라 알고리즘은 항상 노드 주변의 최단 경로를 선택한다. 즉, 이미 최단 경로로만 왔는데 더 짧은 경로가 존재했다면 다익스트라 알고리즘의 논리가 무너진다.

그래서 음수 가중치가 있는 경우, 음수 가중치를 양수로 변환하거나 음수 가중치를 계산할 수 있는 다른 알고리즘을 사용해야 한다.

 

위에서 언급한 것과 같이 다익스트라 알고리즘은 항상 노드 주변의 최단 경로를 선택해서 최장 거리를 구하고 싶을 때는 다익스트라 알고리즘을 사용할 수 없다.

 

그래서 나는 이 슬로우로드 내비게이션 서비스가 어떤 알고리즘을 사용할지 궁금했다. 최장 거리로 가는건지, 어떤 경치를 감상한다는 건지..

 

오픈 베타 버전으로 먼저 선보이는 ‘슬로우로드’ 서비스는 제주공항과 중문, 서귀포, 성산 등 제주도 내 7개 권역을 연결해주는 50개 경로를 제공한다. 50개의 슬로우로드는 경로에 따라 적게는 5곳, 많게는 11곳의 장소를 경유하는 우회 길이라는 점이 특징이다. 제주도청과 제주관광공사의 관광 데이터를 기반으로 선정된 경유지에는 기존에 알려진 관광 명소 외에도 제주지역 곳곳에 숨겨진 아름다운 장소들이 포함됐다. 가령, 제주공항에서 성산 일출봉으로 이동할 경우 내비게이션은 주로 97번 도로(번영로)와 1119번 국도(서성로)를 지나는 빠른 길을 추천하지만, 슬로우로드는 아침미소목장, 한라생태숲, 안돌오름 등을 경유하는 경로로 안내해준다. 이 경로는 빠른 길 대비 목적지까지 40여 분 정도 더 걸리는 대신, 여행객들을 제주도 내 다양한 여행지로 분산시키고 새로운 장소를 여행하는 기회를 제공한다는 점에 의의가 있다.

 

저번에는 제목만 보고 넘어가서 위와 같은 궁금증이 일었는데, 오늘 기사를 읽어보고 알게 됐다. 50개의 경로를 제공한다는건 대표적인 관광지를 미리 뽑아놓고, 시작과 끝에 따라 중도에 방문할 수 있는 관광지 후보를 넣어놓고 빠른 길을 제외한 경로 중에 선택을 하라고 하겠구나 라고..

 

하긴 최장거리로 가려면 밑도 끝도 없긴 하다. 아무튼 재밌는걸 만든 것 같다. 중학교까지 제주도에 살다가 육지에 이사와서 어쩌다보니 계속 안가고 있는데 오랜만에 다시 가서 고향 친구들을 만나고 싶다.