[Algorithm] 백트랙킹 이해 + example

1. 백트랙킹 과 DFS

- DFS는 무한히 깊은 곳을 찾아야할 때 효과적이다. 하지만 DFS는 모든 곳을 방문하기 때문에, 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수 있다

 

- 이렇게 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 있는 루트를 검사하는 방법이 백트랙킹

=> DFS에 pruning을 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법

 

[ 4가지의 절차 ]

1. DFS 수행 - DFS를 수행하여 노드를 찾는다

2. 유망한 노드 검토 - 유망한 노드이면 서브트리로 이동. 그렇지 않으면 백트랙킹

3. 서브트리 이동 - 방문한 노드의 하위로 이동하여 다시 DFS 수행

4. 백트랙킹 수행 - 방문한 노드로 가지치기하고, 상위 노드로 백트랙킹 한 후 DFS 다시 수행

 

 

 

[ 완벽히 숙지 해야할 것]

1. 재귀로 DFS구현하는 것

2. 백준 N과 M 시리즈

3. n-queens 문제

4. 백준 #1182 부분수열의 합

 

풀어보기