[Algorithms] Mazing Problem | 미로 찾기 문제

Mazing Problem

미로 찾기 문제

---

Mechanism (원리)

Figure	Description
	- 주어진 미로이다. - S는 시작지점, T는 목표 지점을 의미한다.
	- 미로를 탐색하는 과정에서 다수의 경로 중 하나를   선택해야 하는 지점(분기점, O 도형)을 표시한다.
	- 위에서 분기점들을 Node로 하고,   시작 지점 S를 Root로 하는 상태 공간 트리를 만들 수 있다. - S에서 시작하여 Child로 내려가며 탐색을 하되,   분기점에 다다르면, 선택지 중 하나를 골라서 탐색한다. - 그림의 회색 도형들은 운 좋게 방문하지 않고,   탐색이 종료된 노드들이다. - 운이 좋으면 시행착오를 겪지 않고 T에 도달할 수 있고,   운이 나쁘면, 모든 노드들을 다 방문한 후에 T에 도달할 수도 있다. - 이 알고리즘을 사실상 DFS와 동일하다.

 

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

maze(v)
{
    visited[v] = TRUE;
    if (v == destination)
        return "Success";
        
    for(x ∈ L(v))
        if(visited[x] == FALSE) {
            prev[x] = v;
            maze(x);
        }
}

---

Performance (성능)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)