[CS]백트래킹(Back Tracking)

선행

• 재귀 / DFS에 대한 학습 필요

백트래킹 : Back Tracking

• 재귀(DFS)적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식
• 가지치기(Pruning): 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 유망(Promising)하지 않다 판단되면 이전 상태로 돌아가는 것
  • DPS를 통해 모든 노드를 탐색하며, 필요 없는 부분을 쳐내는 행위

백트래킹 예제

• 백트래킹 이해를 위해서는 BOJ N과 M 시리즈 문제를 모두 풀면 됨

1. BOJ 15649 N과 M (1)

https://velog.io/@hyeon23/BOJN%EA%B3%BC-M-1

2. BOJ 15650 N과 M (2)

https://velog.io/@hyeon23/BOJN%EA%B3%BC-M-2

3. BOJ 15651 N과 M (3)

https://velog.io/@hyeon23/BOJ15651-N%EA%B3%BC-M-3

4. BOJ 15652 N과 M (4)

https://velog.io/@hyeon23/BOJ15652-N%EA%B3%BC-M-4

5. BOJ 15654 N과 M (5)

https://velog.io/@hyeon23/BOJ15653-N%EA%B3%BC-M-5

6. BOJ 15655 N과 M (6)

https://velog.io/@hyeon23/BOJ15655-N%EA%B3%BC-M-6

7. BOJ 15656 N과 M (7)

https://velog.io/@hyeon23/BOJ15655-N%EA%B3%BC-M-7

8. BOJ 15657 N과 M (8)

https://velog.io/@hyeon23/BOJ15655-N%EA%B3%BC-M-8