문제 해결 과정의 중간 사태를 각각 한 노드로 나타낸 트리
문제 풀이가 진행된 상태를 노드로 나타낸 것
탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는 방법
DFS는 백트랙킹의 골격을 이루는 알고리즘
상태공간 트리의 루트에서 시작해서 DFS 방식으로 탐색을 해나가는 것과 대응
주로 재귀적으로 구현
미로찾기 문제
알고리즘
maze(v){
visited[v] == YES;
if(v==T) then {return "성공";} //끝내기
for each x in L(v) //L(v)은 정점 v와 인접한 정점 집합
if(visited[x] == NO) then{
prev[x] = v;
maze(x);
}
}