내비게이션은 어떻게 1초 만에 '가장 빠른 길'을 찾아낼까?
여러분, 운전하는 부모님 옆에 타본 적 있나요? 출발지와 목적지를 입력하자마자 내비게이션은 거짓말처럼 순식간에 "가장 빠른 길"을 알려줍니다. 서울에서 부산까지 갈 수 있는 길이 수백, 수천 가지가 넘을 텐데 말이죠. 컴퓨터가 그 많은 길을 전부 다 가보고 비교하는 걸까요? 그렇다면 1초는커녕 몇 시간이 걸려도 이상하지 않을 텐데요.
사실 이 마법 같은 계산 뒤에는 1959년, 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 만든 아주 우아한 수학적 아이디어가 숨어 있습니다. 바로 다익스트라 알고리즘입니다.
지도를 점과 선으로
바꿔보기:그래프 이론
먼저 지도를 수학적으로 다시 그려볼게요. 수학에서는 이걸 그래프(Graph)라고 부릅니다. 여기서 그래프는 우리가 아는 막대그래프, 꺾은선그래프가 아니라, 교차로 같은 지점들을 정점(Vertex)으로, 그 사이를 잇는 도로를 간선(Edge)으로 표현한 구조를 말해요. 그리고 각 도로(간선)에는 거리나 걸리는 시간 같은 '가중치(Weight)'가 붙습니다.
즉, 우리 동네 지도도 사실은 점과 선, 그리고 숫자로 이루어진 거대한 그래프인 셈이죠. 내비게이션의 목표는 이 그래프 안에서 출발 정점부터 도착 정점까지 가중치의 합이 가장 작은 경로를 찾는 것입니다.
다익스트라의 똑똑한 전략:
욕심쟁이처럼,
그러나 확실하게
핵심 아이디어는 생각보다 간단합니다. "지금까지 확인한 길 중에서, 가장 가까운 곳부터 차례로 확정해나가자!"
- 출발점에서 각 지점까지의 거리를 '무한대'로 일단 두고, 출발점 자신은 0으로 설정합니다.
- 아직 방문하지 않은 지점 중, 현재까지 알려진 거리가 가장 짧은 지점을 선택합니다.
- 그 지점을 거쳐서 이웃 지점들로 갈 때, 기존에 알던 거리보다 더 짧아지는 경로가 있다면 거리를 업데이트(이걸 '완화(Relaxation)'라고 부릅니다)합니다.
- 모든 지점을 방문할 때까지, 혹은 목적지에 도달할 때까지 이 과정을 반복합니다.
이렇게 하면 재미있게도, 한 번 "확정"된 최단 거리는 절대 나중에 바뀌지 않는다는 게 수학적으로 증명되어 있습니다. 이미 확정된 거리보다 더 짧은 경로가 나중에 나올 수 없기 때문이죠. 이 성질 덕분에 모든 경로를 일일이 다 확인하지 않고도 최단 경로를 확실하게 찾아낼 수 있는 겁니다. 마치 욕심쟁이처럼 눈앞의 가장 좋은 선택만 반복했는데, 결과적으로는 전체 최적해가 되는 신기한 알고리즘이죠.
직접 해보는 실습:
5개 도시 최단 경로 찾기
이제 여러분이 직접 손으로 다익스트라 알고리즘을 돌려볼 차례입니다! 아래와 같은 5개의 도시(A, B, C, D, E)가 도로로 연결되어 있다고 해봅시다. 숫자는 두 도시 사이의 거리(km)입니다.
A - B : 4 A - C : 1 C - B : 2 B - D : 5 C - D : 8 C - E : 4 D - E : 1
질문: A에서 출발해서 E까지 가는 가장 짧은 거리는 몇 km일까요?
풀이 과정 (표로 따라가기)
단계 | 확정된 도시 | A까지 거리 | B까지 거리 | C까지 거리 | D까지 거리 | E까지 거리 |
시작 | - | 0 | ∞ | ∞ | ∞ | ∞ |
1 | A (0) | 0 | 4 | 1 | ∞ | ∞ |
2 | C (1) | 0 | 3 (1+2) | 1 | 9 (1+8) | 5 (1+4) |
3 | B (3) | 0 | 3 | 1 | 8 (3+5) | 5 |
4 | E (5) | 0 | 3 | 1 | 8 | 5 |
5 | D (6) | 0 | 3 | 1 | 6 (5+1) | 5 |
힌트: 2단계에서 A→B는 원래 4였지만, A→C→B(1+2=3)가 더 짧아서 값이 업데이트됩니다. 이게 바로 '완화(Relaxation)' 과정이에요!
정답: A에서 E까지 가장 짧은 경로는 A → C → E, 총 거리 5km입니다 (1km + 4km). 얼핏 보면 여러 도시를 거쳐가는 경로가 더 빨라 보일 수 있지만, 표를 따라가 보면 C를 거쳐 곧장 E로 가는 길이 가장 효율적이라는 게 확인되죠.
직접 종이에 그래프를 그리고, 표를 채워가며 손으로 풀어보세요. 컴퓨터가 하는 계산과 원리는 완전히 똑같답니다!
실생활 곳곳에 숨어있는
다익스트라
이 알고리즘은 단순히 자동차 내비게이션에만 쓰이지 않습니다.
- 인터넷 라우팅: 여러분이 보낸 카카오톡 메시지가 인터넷망의 수많은 경로 중 가장 빠른 길을 찾아 전달되는 과정에도 비슷한 원리가 쓰입니다.
- 게임 캐릭터의 길 찾기: RPG 게임에서 몬스터나 NPC가 장애물을 피해 플레이어에게 다가올 때도 그래프 탐색 알고리즘이 작동합니다.
- 최단 배송 경로: 택배 회사가 여러 배송지를 가장 효율적인 순서로 도는 경로를 짤 때도 그래프 이론이 기초가 됩니다.
왜 우리가 이걸 배워야 할까?
다익스트라 알고리즘은 복잡한 미적분이나 어려운 공식이 필요하지 않습니다. 필요한 건 논리적으로 문제를 쪼개고, 규칙을 세워 반복하는 사고방식뿐입니다. 이것이 바로 수학이 단순히 시험 문제를 푸는 도구가 아니라, 세상을 더 효율적으로 이해하고 설계하는 언어라는 걸 보여주는 좋은 예시입니다.
다음번에 내비게이션이 "경로를 안내합니다"라고 말할 때, 그 뒤에서 수많은 점과 선, 그리고 숫자들이 눈 깜짝할 사이에 정렬되고 있다는 걸 떠올려보세요. 여러분이 지금 배우는 수학이, 사실은 이미 여러분의 일상 곳곳에서 조용히 작동하고 있답니다.
