[6월의 퍼즐] HORIZON 미로

미로의 ‘미’는 한자로 미혹할 미^迷를 쓰며 뜻을 풀이하면 ‘헷갈리는 길’ 정도로 읽을 수 있겠다. 헤매지 않고 미로를 빠져나오려면 어떻게 해야 할까?

미로를 공략하는 확실한 방법 중 하나는 트레모 알고리즘^{Trémaux’s algorithm}으로, 자기가 지나간 길을 표시하여 갔던 곳을 또 가지 않게 만드는 방식이다. 가령 지면에 그려진 미로를 연필로 풀어나가다가 이미 선을 그은 부분을 마주쳤을 경우 바로 탐색을 멈추고 이전 분기점으로 되돌아가는 것이다.

혹여나 너무 간단하다고 생각할 여러분을 위해 연필로 선을 긋는 것만으로는 해결하기 어려운 미로를 소개한다. 논리 미로^{Logic maze}, 또는 다중 상태 미로^{Multi-state maze}라 불리는 이 미로들은 특별한 규칙에 따라 움직여야하는 미로들로, 같은 곳을 지나더라도 어떤 때에는 통과할 수 있는 반면 또 어떤 때에는 통과할 수 없도록 설계되어있다.

예시가 궁금한 독자들은 에드 페그 주니어^{Ed Pegg Jr}가 MAA^{Mathematical Association of America}에 쓴 칼럼을 읽어보길 강력히 추천한다.

박부성 교수님께서 2021년 2월 Horizon에 소개하신 ‘미로 속의 암소’의 미로 역시 같은 종류의 미로로 볼 수 있으니 확인하면 좋을 것이다.

여기 필자가 HORIZON을 위해 특별히 만든 미로가 있다. 미로의 규칙은 다음과 같다.

1. 미로를 들어가 H-O-R-I-Z-O-N-H-O-R-I-…-Z-O-N 순으로 알파벳을 밟고 나온다. 시작은 H, 끝은 N이어야한다.

2.

 – 왼쪽 알파벳 발판의 경우 ‘가, 다’로 들어가면 I, ‘나, 라’로 들어가면 H로 읽는다.
 – 오른쪽 알파벳 발판의 경우 ‘가, 다’로 들어가면 Z, ‘나, 라’로 들어가면 N으로 읽는다.
 – R, O는 어느 쪽으로 들어가도 R, O로 읽는다.

3. 같은 길, 같은 발판을 여러 번 밟을 수 있지만, 제자리 후진은 불가능하다.

예시를 살펴보자. 아래 미로의 경우 ‘HORIZON’을 두 번 반복한 뒤 미로를 빠져나가면 정답 이다. 같은 길을 여러 번 밟지만 제자리 후진은 하지 않았다.

이제 본격적인 문제이다. 미로를 통과하는 가장 짧은 경로를 찾아주길 바란다.