가장 빠른 길 찾기

선마다 거리가 달라요

점과 점을 선으로 잇는 건 배웠죠.
그런데 길에는 한 가지가 더 있어요.
선마다 거리가 달라요.
어떤 길은 짧고,
어떤 길은 멀어요.
그래서 선 위에 숫자를 적어요.
그 숫자가 바로 거리예요.
아래에서 길을 눌러 거리를 봐요.

길을 눌러 거리를 봐요. (선 = 길 · 숫자 = 그 길의 거리)

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

가까운 순으로만은 안 돼요

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

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

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

가까운 것부터 확정

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

가장 가까운 점을 눌러 확정해요. (매번 미확정 중 최단 거리를 골라요)

이게 눈앞의 최선 고르기예요.
전체 지도를 다 풀어보는 게 아니라,
지금 가장 가까운 점부터
하나씩 확정해 나가요.
한 점을 확정하면,
그 점을 거쳐 가는
이웃 점들의 거리도
새로 가까워질 수 있어요.

경계를 넓혀가요

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

경계 바깥 점을 눌러 영역을 키워요. (확정 영역이 한 점씩 바깥으로 자라요)

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

정리

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

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

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