우선법

대표적인 미로탐색 알고리즘 중 하나. 좌선법을 통해 들어왔는데 우선법이 나왔다고 이상하게 생각할 필요는 없다. 어차피 둘 다 방향만 다를 뿐 원리는 똑같다.

어떤 미로를 빠져 나갈 때, 오른쪽(좌선법은 왼쪽) 벽을 따라 계속 가다 보면 언젠가는 출구에 도달한다는 원리이다. 이 때 왼쪽 오른쪽은 탐색자(traveler)를 기준으로 한다. 탐색자가 뒤돌아서있다면 반대편 벽을 짚을 것이다. 이게 막다른 길을 빠져나가는 우선법 알고리즘의 작동 메커니즘이다. 막다른 길에서 모서리를 따라 계속 손을 짚어나가면 자연적으로 U턴을 하면서 뒤돌아서게 되며 자연스럽게 반대편 벽을 짚는다. 단순하지만 결과만큼은 확실하게 내는 알고리즘.

그런데 이 알고리즘으로 통과가 불가능한 미로가 있다. 아니 사실 상당히 많다. 미로를 그래프 자료구조로 바꿨을 때(교차점을 노드로, 길을 에지로 한다) 사이클이 생기는 미로는 우선법으로 통과할 수 없을 가능성이 생긴다. 사이클이 생긴 그 지점에 들어서면 무한히 맴돌게 된다. 그렇지 않은 미로는 3차원이든 4차원이든 우선법으로 통과할 수 있다.

좀 쉬운 예시를 들면, 미로는 미로인데 미로를 크게 감싸고 도는 외부 담장이 있다고 해 보자. 담장은 아무리 손을 짚어서 따라가더라도 미로 내부로 진입할 수 없다. 이게 우선법 알고리즘의 단점이다. 즉 출구가 미로 한가운데 있는 형태의 미로에서는 우선법 알고리즘을 사용하지 않는게 좋다.

그리고 이 알고리즘은 최단 경로를 찾는 알고리즘이 아니다. 미로탐색 알고리즘에 자세히 서술돼있지만 최단 경로를 찾아내는 알고리즘은 다익스트라 알고리즘이다.

장점은 메모리를 적게 먹는다. 자신이 이미 지나간 길을 체크할 필요가 없기 때문이다. 방문한 지점을 체크하는 우선법 알고리즘은 BFS/DFS알고리즘이라고 해서 우선법과는 다른 알고리즘이다. BFS/DFS알고리즘은 미로의 사이클 형성 여부와 관계없이 출구가 존재한다면 출구로 나간다는 걸 보장한다.