빠져나올 수 없는 미로는 존재할까?

 

확장 좌수법.

 

한 번 갔던 방향의 경로를 체크해두고 다시 왔던 길을 경유하지 않도록 표시하는 방식입니다.

이 중 가장 유명한 트레모 알고리즘이라는 미로 탈출법이 있습니다.

 

갈림길에 나오는 곳에 다다르게 되면 본인이 왔던 길을 다른 위치에서 보아도 알아볼 수 있게끔 표시를 해둡니다.

그리고 갈림길에서 2개의 표시가 되어있는 통로는 가지 않습니다.

마지막으로 표시가 가장 적게된 곳으로 경로를 지정하여 통로마다 위 서술한 방법대로 표시하면서 길을 다닙니다.

 

이 방법을 사용하면 복잡한 길을 단순화시키는 것이 가능하다고 합니다.

 

일반화되어 형식으로 나와있는 다른 미로탈출 방법들을 실제로 사용하면 탈출하는 것이 거의 가능하다고 하나, 해결하기 도저히 탈출하기 힘든 미로라면 어떨까요?

 

특히나 게임이나 만화에서 등장하는 실시간으로 변형되는 미로는 굉장히 골칫덩어리겠죠.

물론 현실에서 이러한 미로를 만드는 방법도 복잡하므로 만들 이유도 없습니다.