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

[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 == T) 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)

728x90

from http://dad-rock.tistory.com/691 by ccl(A) rewrite - 2021-09-11 14:26:33