미로 알고리즘 보면서 생각해본 또다른 미로 해법

얘는 로봇에게 계산을 요구하는 그런 알고리즘이 아니라 미로 전체에다가 덧씌우는 알고리즘이라고 볼 수 있는데

일단 미로는 평범하게 격자식으로 만듭니다.

그 다음에 로봇을 시작위치에 두고 미로를 맨 첫번째 칸부터 차례대로 검사합니다.

벽이 1, 2, 4개인 경우는 그냥 지나갑니다.

그런데 만약 검사한 칸의 벽이 3개면 그 곳은 막다른 길이라는 뜻이겠죠?

막다른 길은 가봤자 아무런 이득이 없으므로 그 칸을 메꿔서 사방을 벽으로 만들어버리고 이전에 뚫려있었던 칸으로 간 다음에 재귀함수를 이용해서 다시 벽이 3개인지 검사합니다.

이런 식으로 쭉 하다보면 아랫글처럼 외벽과 내벽이 분리되어 있는 상황이 아닌 이상 길이 엄청나게 단순하게 바뀌겠죠?

물론 외벽과 내벽이 분리되어 있는 경우는 따로 알고리즘을 써서 메꿔주도록 합니다.

이 과정을 전부 다 마치면 미로는 더 이상 미로라고 부를 수 없을 정도로 간략화되어있을 것이고, 로봇한테는 간략화된 미로의 탈출로를 따라가도록만 설정해주면 될 것입니다.

너무나도 재밌는 알고리즘이군요! 상당한 시간이 걸리겠지만 말이죠.

...라고 생각했는데 내가 생각해낼 수준의 알고리즘이라면 논문은 고사하고 책도 나왔을 거야

흑흑 

전체를 스캔하는 방법이라니...

스투 길찾기 인공지능