상태 공간 트리 (State-Space Tree)

문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리를 상태 공간 트리(State-Space Tree)라고 한다. 이러한 상태 공간 트리를 탐색하는 방식들에 대해서 이야기 하고자 한다. 1. 백트래킹 (Backtracking) 백트래킹은 주어진 상태 공간 트리를 트리의 루트에서 시작해서 DFS 방식으로 탐색을 해 나가는 것이다. 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었다고 한다. 대표적으로 미로 찾기 문제와 색칠 문제가 있다. 미로 찾기 문제 만약 우리가 미로에 갇히게 되면 어떻게 탈출해야할까? 갈 수 있는곳을 일단 가보고, 막다른길이 있다면 왔던길을 되돌아와 가보지 않은 길을 선택하는 행동을 출구가 나올때 까지 반복할 것이다. 미로 -> 상태 ..