d라이브러리

한결이가 수호에게 첫 과제를 내놨어요. 학교까지 가는 가장 빠른 길을 찾는 거죠. 이건 바로 ‘최단 경로 알고리즘’을 익히는 과정이랍니다.

최단 경로 알고리즘은 주어진 지점들을 잇는 가장 ‘빠른 길’을 찾는 알고리즘이에요. 지하철 환승 경로 찾기, 대중교통과 자동차에 맞는 빠른 길 찾기뿐만 아니라 도시에 건물을 배치하거나 회로를 설계할 때도 이용되지요. 최단 경로 알고리즘은 각 지점과 그 지점들을 잇는 경로를 점과 선으로 간단하게 표시하는 데서 시작해요. 그리고 길의 길이, 이동 시간, 이동하는 데 드는 비용 등 관련된 모든 항목을 수치로 만들지요. 이 수치를 ‘가중치’라고 해요. 가중치가 가장 적은 길이 바로 가장 빠른 길이랍니다.

가장 많이 쓰이는 ‘다익스트라 알고리즘’을 이용해 수호의 집에서 학교까지 가는 길을 한 번 살펴볼까요?

일단 집과 학교, 그 사이에 있어서 거쳐 갈 수 있는 지점들을 점으로 표시하고, 각 지점을 연결하는 선에 가중치를 넣어 줘요. 수호 집과 학교 사이에는 공원과 대형 마트가 있는데, 공원까지는 걸어갈 수 있지만 마트는 마을버스를 타야 해요. 그럼 마트까지 가는 데 비용이 더 들기 때문에 가중치를 더 두는 식이에요.

이제 각 거리의 가중치를 바탕으로 빠른 길을 찾아볼게요. 집에서 학교까지 바로 가는 길은 일반 버스를 타고 꼬불꼬불한 길을 따라가야 하기 때문에 가중치를 10으로 뒀어요. 반면 집-공원, 공원-학교는 각각 지름길이 있어서 시간이 줄어들어요. 그래서 각각 가중치를 3과 4로 뒀지요. 대형 마트를 거쳐 가는 길도 마찬가지로 계산해서 5와 6으로 가중치를 뒀어요. 결국 가장 빠른 길은 가중치가 7로 가장 적은 공원을 거쳐 가는 길이지요.
 

방금 검토한 길은 점이 네 개밖에 없어서 간단하게 끝났어요. 하지만 각 지점과 이 점들을 잇는 경로가 늘어나면 어떻게 해야할까요? 일단 지점과 경로를 점과 선으로 간단하게 표시하고, 모든 지점들을 거리 순으로 늘어놓은 표를 만들어요. 그리고 한 지점을 거칠 때마다, 최종 목적지까지 걸리는 거리를 계속 수정하며 가장 가중치가 적은 경로를 찾는 거예요.

예를 들어 수호 집과 학교 사이에 공원, 마트, 은행, 한결이 집이 있다고 해 봐요. 그러면 이 네 군데를 거쳐가는 길을 하나씩 그려가며 학교까지 걸리는 가중치를 각각 계산하는 거지요. 이런 식으로 아무리 복잡한 지도에서도 최단 경로를 쉽게 찾을 수 있답니다.

최단 경로는 상황에 따라 다를 수도 있어요. 예를 들어 A에서 B로 이동하는 길이 두 군데가 있다고 해요. 첫 번째길은 꼬불꼬불 좁은 길을 돌아가서 10km가 걸리고, 두 번째 길은 5km짜리 직선 도로로 시원하게 뚫려 있어요. 하지만 직선 도로는 오가는 차가 많고, 신호등도 굉장히 많이 설치돼 있기 때문에 교통량이 많은 시간대에는 차가 막힐 수 있어요. 이 경우 평소에는 두 번째 길이 좋지만, 교통량이 많을 때는 첫번째 길이 최단 경로가 되지요. 내비게이션이 교통량을 바로바로 확인해 안내하는 길을 계속 바꾸는 이유랍니다.