05. 바둑판 미로와 최단 경로 알고리즘
1. 학습 목표 (Learning Objectives)
- 도시의 바둑판 같은 도로망에서, 뒤로 돌아가지 않고 가장 빠르게 목적지로 가는 ‘최단 경로(Shortest Path)’의 경우의 수를 구하는 방법을 익힙니다.
- 각 교차로마다 도달하는 숫자를 덧셈(+)하여 더해가는 방식이, 인공지능 내비게이션의 길 찾기 알고리즘의 초기 모델임을 이해합니다.
2. A 지점에서 B 지점으로: 뒤돌아보지 마라
도로망이 바둑판처럼 반듯하게 짜여 있는 미래의 사이버펑크 도시를 상상해 보겠습니다. 집(A)에서 학교(B)까지 가야 하는데, 조건은 무조건 ‘최단 거리(최소 블록)’ 이어야 합니다.
최단 거리의 절대 규칙은 단 두 가지입니다.
“무조건 오른쪽($\rightarrow$), 아니면 위($\uparrow$)로만 직진해야 한다. 단 한 번이라도 왼쪽이나 아래로 등을 돌려 후퇴하면 최단 거리를 실패한다!”
무조건 전진만 해야 하는 이 압박감 속에서, 내가 학교까지 도달할 수 있는 ‘안전한 최단 경로의 가짓수’는 도대체 몇 개일까요?
3. 길 찾기의 마법, 꼭짓점 덧셈 법칙
복잡한 공식을 외울 필요가 전혀 없습니다! 자동차 내비게이션 AI가 작동하는 가장 기초적인 원리인 ‘합의 법칙 누적 스캔’ 만 알면 끝납니다.
학교로 가는 길목의 어떤 교차로 점 P 에 도달했다고 생각해 봅시다. 나의 궤적 법칙상, 이 점 P로 들어올 수 있는 길은 무조건 딱 두 군데뿐입니다.
- 내 ‘왼쪽 교차로’에서 오른쪽으로 진입해 들어오거나!
- 내 ‘아래쪽 교차로’에서 위쪽으로 진입해 들어오거나!
★ 최단 경로 덧셈의 원리
현재의 교차로(P)까지 도달하는 모든 경우의 수는 = (왼쪽 교차로까지 오는 경우의 수) + (아래쪽 교차로까지 오는 경우의 수) 로 완벽하게 100% 귀결폭발합니다!
이 단순무식한 진리를 알게 된 당신은, 이제 집(A)에서 출발하여 바둑판의 맨 겉테두리 교차로마다 1, 1, 1... 이라는 초기 숫자를 적어둔 뒤, 내부 교차로를 만날 때마다 왼쪽 숫자 + 아래쪽 숫자를 합쳐서 새 숫자를 적어 나가며 거대한 다이내믹 프로그래밍(DP) 피라미드를 쌓아 올릴 수 있습니다!
이 숫자들의 누적 스캔 배열은 곧 천재 파스칼이 발견한 거대한 경우의 수 건축물, ‘파스칼의 삼각형(Pascal’s Triangle)’ 속 계수 패턴과 일치하는 미친듯한 수학적 아름다움을 보여줍니다.
4. 학습 정리 (Summary)
- 최단 경로 알고리즘: 후퇴를 허용하지 않는 방향성을 가진 길 찾기 모델에서, 모든 경우의 수는 ‘합의 법칙(OR)’을 통해 왼쪽에서 진입한 경로 수와 아래에서 진입한 경로 수를 지속해서 누적 덧셈하는 방식으로 거대한 경우의 수를 토해냅니다.
- 다중 경로의 누적 연산: 컴퓨터 알고리즘과 인공지능이 복잡한 트래픽 맵 타일에서 최단 경로를 탐색할 때 사용하는 2D 배열 계산(다이내믹 프로그래밍)의 극히 아름답고 정석적인 초기 형태입니다.