어떻게 가장 빠른 길 찾기

선마다 거리가 다르다

점과 점을 선으로 잇는 법은 이미 배웠다. 그런데 실제 길에는 한 가지가 더 있다. 선마다 거리가 다르다는 것이다.
어떤 길은 짧고 어떤 길은 멀어서, 선 위에 숫자를 적는다. 그 숫자가 바로 거리다.
아래에서 길을 눌러 거리를 확인해요.

길을 누르면 거리가 보인다. (선 = 길 · 숫자 = 그 길의 거리)

거리가 다르다는 것이 왜 중요할까? 갈림길을 적게 거치는 길이라도 한 칸 한 칸이 멀면 전체로는 더 느릴 수 있다.
반대로 갈림길을 더 거쳐도 각 칸이 가까우면 전체로는 더 빠를 수 있다.
그러니 거리를 빼고 길을 고를 수는 없어요.

가까운 순서로 세기만으로는 부족하다

앞에서 가까운 순서로 퍼지는 방법을 보았다. 한 칸, 두 칸, 세 칸, 출발점에서 몇 칸 떨어졌는지로 세는 방법이었다.
그런데 그것은 모든 길이 똑같이 한 칸일 때의 이야기다.
길마다 거리가 다르면 칸 수가 적은 길이 꼭 더 가까운 것은 아니에요.

두 길을 눌러 견준다. (칸 적은 길 vs 거리 짧은 길 · 같지 않아요)

갈림길을 적게 거친 길이 거리로는 더 멀었다. 칸 수만 세면 이 함정에 빠진다.
그래서 칸 수가 아니라 거리를 더해 가며 진짜 가까운 길을 찾아야 해요.

가까운 것부터 확정한다

그럼 어떻게 할까? 눈앞의 최선을 고르는 탐욕을 떠올려 보자.
출발점에서 시작해, 아직 거리가 확정되지 않은 점들 가운데 지금 가장 가까운 점 하나를 골라 그 거리를 확정한다.
길의 거리가 음수가 아니라면 가장 가까운 점까지 더 짧은 길이 있을 수 없으니, 확정해도 안심이에요.

가장 가까운 점을 눌러 확정한다. (매번 미확정 점 가운데 거리가 가장 짧은 것을 고른다)

이것이 눈앞의 최선 고르기다. 전체 지도를 다 풀어 보는 것이 아니라 지금 가장 가까운 점부터 하나씩 확정해 나간다.
한 점을 확정하면 그 점을 거쳐 가는 이웃 점들의 거리도 새로 가까워질 수 있다.
이 방법을 다익스트라 알고리즘이라고 불러요.

경계를 넓혀 간다

확정한 점이 늘어날수록 '거리가 정해진 영역'이 생기고, 그 영역의 가장자리가 경계다.
매번 경계 바로 바깥에서 가장 가까운 점을 하나 끌어들이면 영역이 한 점씩 커진다.
잔잔한 물에 돌을 던지면 물결이 퍼지는 것과 닮았어요.

경계 바깥 점을 누르면 영역이 커진다. (확정 영역이 한 점씩 바깥으로 자란다)

경계가 점점 바깥으로 퍼지다 보면 언젠가 모든 점이 확정 영역 안에 들어온다.
그때면 출발점에서 어느 점까지든 가장 빠른 거리를 다 알게 된다. 가까운 데부터 차근차근, 그것이 비결이에요.

정리

가장 빠른 길 찾기를 한 줄로 모으면 이렇다. 선마다 거리가 다르면 칸 수가 적은 길이 곧 빠른 길은 아니어서, 가까운 순서로 세기만으로는 부족하다.
가까운 점부터 거리를 확정하고 경계를 한 점씩 넓혀 가면, 매 순간 눈앞의 최선을 고르면서 모든 점까지의 최단 거리를 찾아요.

핵심을 차례로 눌러 정리해요. (거리 다름 → 칸 수론 안 됨 → 가까운 것부터 확정 → 경계 넓힘)

지도 앱이 가장 빠른 길을 찾아 줄 때 속에서는 이런 일이 일어난다. 가까운 곳부터 거리를 확정하며 경계를 조금씩 넓히는 것이다.
눈앞의 최선이라는 단순한 규칙이, 거리가 제각각인 복잡한 길에서도 가장 빠른 답을 데려와요.