어떤 미로를 빠져 나갈 때, 오른쪽(좌선법은 왼쪽) 벽을 따라 계속 가다 보면 언젠가는 출구에 도달한다는 원리이다. 이 때 왼쪽 오른쪽은 탐색자(traveler)를 기준으로 한다. 탐색자가 뒤돌아서있다면 반대편 벽을 짚을 것이다. 이게 막다른 길을 빠져나가는 우선법 알고리즘의 작동 메커니즘이다. 막다른 길에서 모서리를 따라 계속 손을 짚어나가면 자연적으로 U턴을 하면서 뒤돌아서게 되며 자연스럽게 반대편 벽을 짚는다. 단순하지만 결과만큼은 확실하게 내는 알고리즘.
그런데 이 알고리즘으로 통과가 불가능한 미로가 있다. 아니 사실 상당히 많다. 미로를 그래프 자료구조로 바꿨을 때(교차점을 노드로, 길을 에지로 한다) 사이클이 생기는 미로는 우선법으로 통과할 수 없을 가능성이 생긴다. 사이클이 생긴 그 지점에 들어서면 무한히 맴돌게 된다. 그렇지 않은 미로는 3차원이든 4차원이든 우선법으로 통과할 수 있다.
좀 쉬운 예시를 들면, 미로는 미로인데 미로를 크게 감싸고 도는 외부 담장이 있다고 해 보자. 원 안쪽의 가장자리에 손을 짚고 천천히 빙 돌아본다고해도 담장이 원이기 때문에 아무리 손을 짚어서 따라가더라도 미로 내부로 진입할 수 없다. 이게 우선법 알고리즘의 단점이다. 즉 출구가 미로 한가운데 있는 형태의 미로에서는 우선법 알고리즘을 사용하지 않는게 좋다.
그리고 이 알고리즘은 최단 경로를 찾는 알고리즘이 아니다. 미로탐색 알고리즘에 자세히 서술돼있지만 최단 경로를 찾아내는 알고리즘은 다익스트라 알고리즘이다.
우/좌선법으로 최단거리를 찾는 방법이 있긴 하다. 물론 좌/우선법이 기반이기 때문에 사이클이 있거나 출구가 미로 한가운데 떨어져있다면 길을 찾지 못하고, 출구로 가는 길이 둘 이상이여도 최단거리를 장담할 수는 없다.
-
우선법으로 지나간 모든 길을 표시한다.
2. 우선법으로 지나지 않는 모든 길을 막는다.
3. 지나지 않는 길이 막힌 미로에서 좌선법을 이용한다.[1]
위의 방법을 이용해서 미로를 풀도록 만들어진 스크래치 프로젝트가 있다. 링크
장점은 메모리를 적게 먹는다. 자신이 이미 지나간 길을 체크할 필요가 없기 때문이다. 방문한 지점을 체크하는 우선법 알고리즘은 BFS/DFS 알고리즘이라고 해서 우선법과는 다른 알고리즘이다. BFS/DFS알고리즘은 미로의 사이클 형성 여부와 관계없이 출구가 존재한다면 출구로 나간다는 걸 보장한다.
[1]
우선법은 오른쪽, 앞쪽, 왼쪽순으로 우선 순위를 둔다. 즉, 우선법으로 지나간 길의 흔적이 오른쪽, 앞쪽, 왼쪽에 모두 있다면 오른쪽과 위쪽은 길이 아니다.