주요 내용
경로 찾기
때때로, 아주 다르게 들리는 문제들의 해결 방법을 생각하다 보면 비슷한 문제로 귀결되는 경우가 있습니다. 팩맨(Pac-Man), 영국의 왕족, 그리고 올랜도(Orlando) 로 운전하는 것의 공통점이 무엇일까요? 이들 모두 경로 찾기 또는 길 찾기 문제와 관련이 있습니다.
- 1693년에 윌리엄 메리 대학을 세운 윌리엄 왕 3세와 현 윌리엄 왕자의 관계는 어떻게 될까요?
- 유령이 팩맨에 가장 빨리 다다를 수 있는 경로는 무엇일까요?
- 텍사스 달라스에서 플로리다 올랜도까지 차로 가는 가장 빠른 길은 무엇일까요?
위 질문에 답하려면 정보가 있어야 합니다.
예를 들어, 영국 왕족의 가계도를 보면 혈연이 있는 사람들 간의 관계를 알 수 있습니다. 윌리엄 왕자는 찰스 필립 아서 윈저의 아들입니다. 찰스는 엘리자베스 2세 여왕의 아들이죠. 문제는 이런 직접적 관계를 이용하여 윌리엄 왕자와 윌리엄 3세를 연결하는 가까운 경로를 가계도에서 찾는 것입니다. 아래의 가계도에서 알 수 있듯이 꽤 많은 연결을 거쳐야 합니다.
팩맨에서는 미로의 지도가 필요합니다. 다음 지도에서는 미로에서 열려 있거나 닫혀 있는 길을 확인할 수 있습니다. 문제는 검정 사각형 위에서 유령이 팩맨까지 가는 길을 찾는 것입니다.
달라스에서 올랜도로 가는 길을 찾기 위해, 인근 도시 간의 연결과 길을 보여주는 미국 지도를 이용할 수도 있습니다. 달라스에서 올랜도로 직접 가는 길은 없지만 여러 번의 길을 갈아타면 됩니다.
미로 탐색
그중 재미있는 미로에 대해 알아봅시다. 이 게임에서 캐릭터는 미로 안을 다닐 수 있습니다.
사람이 가고자 하는 곳을 클릭하면 컴퓨터는 거기까지 캐릭터를 옮길 방법을 찾습니다. 목적지는 빨간 사각형에 "GOAL"이라고 표시합니다. 캐릭터는 항상 같은 시작 사각형에서부터 시작합니다. 직접 해보세요:
캐릭터가 어떻게 목적지까지 이동했는지 보이시나요? 목적지에 다다르려면 프로그램에서 사용자가 클릭한 곳으로 가기 위해 캐릭터가 따라야 하는 정확한 움직임들을 결정해야 하고 이런 움직임들을 구현해야 합니다. 캐릭터가 가는 길에는 여러 길이 있을 수 있으므로 프로그램은 최선의 경로를 선택해야 합니다.
알고리즘을 결정하기 전에 우선 이동 규칙이 만들어져야 합니다. 벽은 회색 네모로 만들어졌고 가야 할 적절한 위치는 비어 있습니다. 각 단계에서 캐릭터는 한 네모에서 옆에 있는 네모로 움직일 수 있습니다. 캐릭터는 체스의 룩처럼 대각선으로 움직일 수 없습니다.
이 프로그램이 사용하는 알고리즘의 기본은 사용자가 클릭한 목적지에 한 네모씩 가까워지는 것입니다. 그런데 "목표 지점에 가까워진다"는 것은 무슨 뜻일까요? 목표 지점까지 직선으로 움직이게 되면 종종 캐릭터가 벽에 부딪히게 됩니다. 알고리즘은 주변의 네모 중 무엇이 실제로 "목표 지점에 더 가까워지는 곳"인지 결정해야 합니다. 이는 네모마다 캐릭터가 그 정점에서 목표 지점까지 이르기 위해 거쳐야 하는 단계의 최소 횟수를 나타내는 "비용"을 할당함으로써 결정할 수 있습니다. 각 네모에 비용을 할당하는 알고리즘은 다음과 같습니다.
- 목표 네모에서 시작합니다. 목표 지점에서 목표 지점까지 얼마나 걸리나요? 0 단계이므로 목표 지점에 숫자 0이라고 표시합니다.
- 미로에서 목표 지점에서 정확히 한 단계 멀리있는 모든 네모를 찾습니다. 이들을 숫자 1이라고 표시합니다. 이 미로에서 목표 지점이 출구 네모라면 정확히 한 단계 떨어진 네모는 하나밖에 없습니다.
- 이제 목표 지점에서 정확히 두 단계 떨어져 있는 모든 네모를 찾습니다. 이 네모들은 1로 표시했던 네모에서 1 떨어져 있고, 아직 표시되지 않은 네모입니다. 이 네모들을 숫자 2로 표시합니다.
- 목표 지점에서 정확히 세 단계 떨어져 있는 모든 네모를 찾습니다. 이 네모들은 2로 표시했던 네모에서 1 떨어져 있고, 아직 표시되지 않은 네모입니다. 이 네모들을 숫자 3로 표시합니다.
- 이런 식으로 목표 지점에서의 거리가 커지는 순서대로 미로 안의 네모들을 계속 표시합니다. 숫자
결국 알고리즘이 캐릭터의 출발점인 네모를 표시하는 순간이 옵니다. 그러면 프로그램에서는 시작 지점에서 경로를 따라 네모의 숫자가 항상 줄어드는 방향으로 네모들을 선택하여 목표 지점으로의 경로를 찾아냅니다. 숫자들을 네모의 높이라고 생각한다면 내리막길이 될 것입니다.
아래의 비용 표시 알고리즘으로 이 게임을 할 수 있습니다. 이 단계를 다시 시작하려면 "Restart algorithm"을 클릭하세요.
사용자가 시작 네모에서 목표 지점까지 가려면 어떻게 해야 할까요? 네모 표시 알고리즘을 이용하면 시작 네모는 목표 지점에서 13단계 멀리 있습니다. 아래는 캐릭터가 있을 수 있는 위치와 시작지점, 목표 지점 간의 연결과 목표 지점에서 각 위치까지의 가장 짧은 거리를 나타낸 그림입니다.
시작 지점의 남쪽으로 목표 지점에서 12 단계 멀리 있는 네모가 있기 때문에 첫 번째 움직임은 "남쪽" 입니다. 방금 이동한 네모의 남쪽은 11 입니다. 다시 남쪽으로 갑니다. 다시 남쪽인 10으로 갑니다. 동쪽인 9로 갑니다. 동쪽으로 두 번 가서 7로 간 후, 북쪽으로 5번 가서 2에 다다릅니다. 한 번 서쪽인 1로 간 후 마침내 북쪽으로 한 번 가서 목표지점에 이르릅니다.
여기서 이 미로 검색 알고리즘을 정확히 어떻게 구현할 지는 설명하지 않겠습니다. 그렇지만 JavaScript를 이용하여 어떻게 미로와 캐릭터를 표현할 것인지, 또 알고리즘을 어떻게 구현할 것인지 생각해 보는 것은 흥미로운 일이 될 것입니다.
위 자료는 다트머스 대학교 컴퓨터 과학과의 토마스 콜먼(Thomas Cormen) 교수, 데빈 발컴(Devin Balkcom) 교수, 칸아카데미 컴퓨팅 커리큘럼 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.
대화에 참여하고 싶으신가요?
우리가 보는 지도를 데이터로 어떻게 수치화해서 입력하나요?(추천 3 번)
앞서 배운 추측게임에서 배운 이진탑색 알고리즘과 경로 찾기에서 배운 알고리즘을
이용할 수 있나 궁금합니다(추천 2 번)
이진탐색 알고리즘은 정렬된 데이터에서 특정 값을 찾을 때 사용할 수 있습니다.
경로 찾기 알고리즘은 한 단계씩 차근차근 모든 경우의 수를 탐색한 후 가장 최적의 값을 찾아내는 것으로 두 알고리즘의 적용분야가 다르다고 생각합니다.(추천 4 번)
- 이 알고리즘에서 굳이 번호를 매길 때 도착지점에서 부터 매긴 이유가 있나요?
시작지점에서 부터 (0 1 2 3 ...)위에서 말한 규칙대로 번호를 매겨서 도착지점의 번호가 매겨질 시 0 1 2 3 경로를 따라 가면 어떤 문제가 발생하나요?(추천 2 번)- 정확히는 잘 모르겠습니다. 하지만 짧은 제 생각으로는 그렇게 한다면 문제가 생깁니다.
저 알고리즘과 비슷하게 시작지점부터 숫자를 매긴 후에 숫자가 높아지는 경로를 따라 이동하는 알고리즘을 설계했다고 가정을 해보겠습니다.
그러면 1경로가 정해지지 않고 갈래길에서 경우의 수가 발생하기 때문에 결국에 처음 문제 상황으로 원위치될 것입니다.
시작지점에서 숫자를 매기는 알고리즘으로 저 문제를 해결하기 위해서는
도착지점에 매겨지는 숫자가 가장 적은 경로만 남게하는 것과 같이
조금 더 복잡한 알고리즘으로 설계해야할 것 같습니다.(추천 3 번)
저 미로는 간단해서 큰 문제가 없겠지만,
실제 지도 등에서는 길찾긱에 전혀 무관한 부분도 있을것입니다.
그러한 문제를 해소할 수 있는 방법이 무엇이 있을까요?(추천 1 번)- Loop를 돈다거나 목적지와 상관없는 방향으로 가는 경로를 말씀하시는 것 같은데요, 위와 같은 알고리즘을 통해서도 해결될 수 있을 것 같습니다. 결국 그 경로까지의 거리값의 minimum을 생각하기 때문이지요. 더 오래걸리는 경로들은 무시될 것입니다.(추천 10 번)
