때때로, 아주 다르게 들리는 문제들의 해결 방법을 생각하다 보면 비슷한 문제로 귀결되는 경우가 있습니다. 팩맨(Pac-Man), 영국의 왕족, 그리고 올랜도(Orlando) 로 운전하는 것의 공통점이 무엇일까요? 이들 모두 경로 찾기 또는 길 찾기 문제와 관련이 있습니다.
  • 1693년에 윌리엄 메리 대학을 세운 윌리엄 왕 3세와 현 윌리엄 왕자의 관계는 어떻게 될까요?
  • 유령이 팩맨에 가장 빨리 다다를 수 있는 경로는 무엇일까요?
  • 텍사스 달라스에서 플로리다 올랜도까지 차로 가는 가장 빠른 길은 무엇일까요?
위 질문에 답하려면 정보가 있어야 합니다.
예를 들어, 영국 왕족의 가계도를 보면 혈연이 있는 사람들 간의 관계를 알 수 있습니다. 윌리엄 왕자는 찰스 필립 아서 윈저의 아들입니다. 찰스는 엘리자베스 2세 여왕의 아들이죠. 문제는 이런 직접적 관계를 이용하여 윌리엄 왕자와 윌리엄 3세를 연결하는 가까운 경로를 가계도에서 찾는 것입니다. 아래의 가계도에서 알 수 있듯이 꽤 많은 연결을 거쳐야 합니다.
엘리자베스 2세와 윌리엄 3세가 강조 표현된 로열 패밀리 가계도
팩맨에서는 미로의 지도가 필요합니다. This map shows connections between adjacent open squares in the maze—or lack of connections, if there is a wall in between—and the problem is to find a path along black squares that leads the ghost to Pac-Man.
고스트와 팩맨이 강조 표현된 팩맨 미로
달라스에서 올랜도로 가는 길을 찾기 위해, 인근 도시 간의 연결과 길을 보여주는 미국 지도를 이용할 수도 있습니다. 달라스에서 올랜도로 직접 가는 길은 없지만 여러 번의 길을 갈아타면 됩니다.
달라스와 올랜드가 강조 표현된 US 도로 지도

미로 탐색

미로에서 주인공을 클릭으로 목적지까지 조종하는 팩맨과 같은 컴퓨터 게임에 대해 조금 더 알아봅시다. 노란색 동그라미로 된 캐릭터를 움직여 빨간 네모로 표시된 목적지를 향해 가기 위해 여기저기를 클릭해 보세요.
캐릭터가 어떻게 목적지까지 이동했는지 보이시나요? 목적지에 다다르려면 프로그램에서 사용자가 클릭한 곳으로 가기 위해 캐릭터가 따라야 하는 정확한 움직임들을 결정해야 하고 이런 움직임들을 구현해야 합니다. 캐릭터가 가는 길에는 여러 길이 있을 수 있으므로 프로그램은 최선의 경로를 선택해야 합니다.
알고리즘을 결정하기 전에 우선 이동 규칙이 만들어져야 합니다. 벽은 회색 네모로 만들어졌고 가야 할 적절한 위치는 비어 있습니다. 각 단계에서 캐릭터는 한 네모에서 옆에 있는 네모로 움직일 수 있습니다. 캐릭터는 체스의 룩처럼 대각선으로 움직일 수 없습니다.
Here's the idea behind the algorithm that this program uses: move 1 square closer to the goal—the place the user clicked on—in each step. 그런데 "목표 지점에 가까워진다"는 것은 무슨 뜻일까요? 목표 지점까지 직선으로 움직이게 되면 종종 캐릭터가 벽에 부딪히게 됩니다. 알고리즘은 주변의 네모 중 무엇이 실제로 "목표 지점에 더 가까워지는 곳"인지 결정해야 합니다. 이는 네모마다 캐릭터가 그 정점에서 목표 지점까지 이르기 위해 거쳐야 하는 단계의 최소 횟수를 나타내는 "비용"을 할당함으로써 결정할 수 있습니다. 각 네모에 비용을 할당하는 알고리즘은 다음과 같습니다.
  1. 목표 네모에서 시작합니다. 목표 지점에서 목표 지점까지 얼마나 걸리나요? 0 단계이므로 목표 지점에 숫자 0이라고 표시합니다.
  2. 미로에서 목표 지점에서 정확히 한 단계 멀리있는 모든 네모를 찾습니다. 이들을 숫자 1이라고 표시합니다. 이 미로에서 목표 지점이 출구 네모라면 정확히 한 단계 떨어진 네모는 하나밖에 없습니다.
  3. 이제 목표 지점에서 정확히 두 단계 떨어져 있는 모든 네모를 찾습니다. 이 네모들은 1로 표시했던 네모에서 1 떨어져 있고, 아직 표시되지 않은 네모입니다. 이 네모들을 숫자 2로 표시합니다.
  4. 목표 지점에서 정확히 세 단계 떨어져 있는 모든 네모를 찾습니다. 이 네모들은 2로 표시했던 네모에서 1 떨어져 있고, 아직 표시되지 않은 네모입니다. 이 네모들을 숫자 3로 표시합니다.
  5. 이런 식으로 목표 지점에서의 거리가 커지는 순서대로 미로 안의 네모들을 계속 표시합니다. 숫자 k로 네모를 표시한 후 k로 표시된 네모들에서 한 단계 멀리 있고 아직 표시가 되어 있지 않은 모든 네모들을 숫자 k, plus, 1라고 표시합니다.
결국 알고리즘이 캐릭터의 출발점인 네모를 표시하는 순간이 옵니다. 그러면 프로그램에서는 시작 지점에서 경로를 따라 네모의 숫자가 항상 줄어드는 방향으로 네모들을 선택하여 목표 지점으로의 경로를 찾아냅니다. 숫자들을 네모의 높이라고 생각한다면 내리막길이 될 것입니다.
아래의 비용 표시 알고리즘으로 이 게임을 할 수 있습니다. 이 단계를 다시 시작하려면 "Restart algorithm"을 클릭하세요.
사용자가 시작 네모에서 목표 지점까지 가려면 어떻게 해야 할까요? 네모 표시 알고리즘을 이용하면 시작 네모는 목표 지점에서 13단계 멀리 있습니다. 아래는 캐릭터가 있을 수 있는 위치와 시작지점, 목표 지점 간의 연결과 목표 지점에서 각 위치까지의 가장 짧은 거리를 나타낸 그림입니다.
미로와 대응되는 그래프
시작 지점의 남쪽으로 목표 지점에서 12 단계 멀리 있는 네모(4행, 3열)가 보이는군요. 그래서 첫 번째 움직임은 "남쪽" 입니다. 방금 이동한 네모의 남쪽은 11 입니다. 다시 남쪽으로 갑니다. 다시 남쪽으로 가서 10으로 갑니다. 동쪽으로 가서 9로 갑니다. 동쪽으로 두 번 가서 7로 간 후, 북쪽으로 5번 가서 2에 다다릅니다. 한 번 서쪽으로 가서 1로 간 후 마침내 북쪽으로 한 번 가서 목표지점에 이르릅니다.
여기서 이 미로 검색 알고리즘을 정확히 어떻게 구현할 지는 설명하지 않겠습니다. 그렇지만 JavaScript를 이용하여 어떻게 미로와 캐릭터를 표현할 것인지, 또 알고리즘을 어떻게 구현할 것인지 생각해 보는 것은 흥미로운 일이 될 것입니다.

위 자료는 다트머스 대학교 컴퓨터 과학과토마스 콜먼(Thomas Cormen) 교수, 데빈 발컴(Devin Balkcom) 교수, 칸아카데미 컴퓨팅 커리큘럼 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.