04. 내비게이션은 어떻게 경로를 찾을까?

<알고리즘 행성 여행자들을 위한 안내서>

최단 경로를 찾아내기 위해 알고리즘이 무엇을 하는지 살펴보자. 참고로, 알고리즘 학자들 사이에서 최단 경로라는 말은 ‘어느 한’ 최단 경로를 뜻하는 것이지, ‘바로 그’ 최단 경로를 뜻하는 게 아니라는 것이 상식으로 통한다. 최단 경로는 동시에 여러 개 존재할 수 있기 때문이다.

내비게이션 장치는 어떻게 가장 빠른 경로를 찾아낼까? 내비게이션 장치에는 교차점과 변들로 이루어진 도로 그래프가 입력돼 있고, 각 변마다 주행 시간이 반영된다. 이 그래프는 매우 상세해서, 실제 주행 시간이 잘 반영돼 있다. 예를 들어, 교차점은 하나의 점이 아니라, 어디에서 출발해 그 교차점까지 가는지, 또 그 교차점에서 시작해 어디까지 계속 주행하려 하는지에 따라 꺾인 여러 개의 변으로 이루어져 있다(내비게이션 장치 및 자동차 제조사들의 능력은 바로 이 주행 데이터의 품질에서 발휘된다). 최단 경로 알고리즘을 위한 입력 데이터는 방향성 있는 그래프와 변의 길이다. 그래프에 방향성이 있다는 것은, 각 변마다 어디가 앞이고 어디가 뒤인지 알 수 있다는 의미다. 일방통행도로도 있으니 말이다. 최단 경로로 가기 위해 우리는 내비게이션 장치의 그래프에서 출발 교차점과 목적 교차점을 선택한 후 차를 출발시키면 된다.

예전에는 사람들이 직접 이 문제를 풀었다. 여기에 대응하는 입력 그래프는 도로 지도책이었다. 여름 휴가지로 향하는 특정 루트, 가령 독일 남부 도시 에어랑엔에서 스페인 바르셀로나까지 가는 길을 찾는 건 그리 어려운 일이 아니다. 보통은 한눈에 척 알 수 있다. 그런데 그 방법이 두 가지 이상 되면 꽤 번거로워진다. 어떤 루트가 더 빠른지 계산해봐야 하기 때문이다. 내비게이션 장치는 이런 작업을 어떻게 해낼까? 그 트릭을 우리가 따라할 수 있을까? 그런데 사실은 그 반대다. 오늘날에도 내비게이션 장치는 도로 지도를 다루는 우리의 트릭을 따라하고 있다.

바르셀로나까지 가는 ‘어느 한’ 경로를 찾기 위해, 내비게이션 장치는 가령 깊이 우선 탐색을 이용해 에어랑엔에서 출발해 나간다. 그리고 목적지인 바르셀로나의 호텔을 찾아낼 때까지 계속 탐색한다. 이때 과제는 정말로 “이보다 더 빠른 경로는 없다”고 보장할 수 있어야 한다는 것이다. 이를 위한 아주 간단한 트릭이 있다. “예외 없이 모든” 경로를 다 살펴보는 것이다. 그런데 이 방법이 정말로 실용적일까?