수학적으로 풀어낸 미로 탈출방법

어느 새 감탄을 한다. 영상을 봤고, 다시 정리를 한다. 치형이에게 미로찾기의 신비로운 경험을 할 수 있도록 써먹기 위하여.

1번째 방법.

위상수학을 활용한다. 흔히 우수법, 좌수법이라고 불린다. 우수법이라 함은 출발지점부터 - 출발지점이 아닌 중간지점부터 사용하면 빙글빙글 돌 수 있다 - 오른쪽 벽면만 쭉 따라가면 미로를 탈출할 수 있다.

이는 위상수학의 원리를 활용한 것이다. 위상수학이란, 물체의 모양을 바꿔도 변하지 않는 기하학적 성질을 연구한 것인데 미로는 결국 두 덩이의 모양만 변한 것이라데서 해법을 찾았다.

2번째 방법.

트레모 알고리즘. 갈림길에서 시작점과 끝지점을 표시한다. 최대한 표시되지 않은 길을 우선한다. 2번 지나간 길이면 색을 달리 해서 표시한다. 그렇게 최대한 표시되지 않았거나 적게 표시된 길을 우선하게 되면 미로를 탈출할 수 있다.

3번째 방법.

에이스타 알고리즘. 최단 거리를 탐색한다. 단, 출발지점과 끝나는 지점을 알고 있어야 사용 가능하다. 분기점을 찍어놓는다. 그 다음, 선택지에서 도착지점에 가까운 분기점을 선택한다. T맵 등 실 생활에서도 활용되고 있다.

미로찾기 실습

김성호 이야기