알고리즘 백트래킹(Backtracking)

●백트래킹

- DFS(깊이우선탐색)방식으로 해를 찾는 방법이다. DFS는 해를 찾기 위해 전진, 후진을 반복한다. 백트래킹 재귀 호출을 해서 구현하면 편리하다.

 

●깊이우선탐색(DFS, Depth First Search)

- 답을 찾을 때 가장 위에서 가장 아래쪽으로 들어 갔다가, 제일 밑에 까지 왔을 때 더 들어갈 곳이 없으면 위로 나왔다가 다시 가장 끝까지 들어가는 동작을 되풀이 한다. 여기서 위로 나오는 동작을 백트래킹이라고 한다

 

●스택(stack)

- 나중에 입력된 데이터가 먼저 빠져 나오는 구조이다. 후입선출(LIFO)

 

●사용하는 재귀함수의 수는 수학의 "경우의 수"와 같다. 예를들어 동전,주사위 등의 문제를 코딩할 때 각각의 무제의 경우의 수만큼의 재귀호출을 사용한다.

 

●백트래킹 알고리즘으로 해결할 수 있는 문제들

1. 미로에서 길 찾기

2. 미로에서 지나간 길에 쓰인 숫자의 합이 최소인 길 찾기

3. 그래프에서 오일러 패스

4. 그래프에서 해밀턴 사이클