[알고리즘] 백트래킹

1. 백트래킹(Backtracking)
   1. 백트래킹에서 사용되는 용어
   2. 백트래킹 예시
      1. 1. N-Queen 문제
         1. 구현 코드
      2. 구현 코드
2. 관련 문제
   1. 문제1. 백준[2839] 설탕 배달
      1. 작성 코드
   2. 문제2. 백준[1931] 회의실 배정
      1. 작성 코드

백트래킹(Backtracking)

모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은
더 이상 구하지 않는 방법

• 정렬된 트리 구조

백트래킹에서 사용되는 용어

• 유망(Promisiong): 해가 될 가능성이 있는 경우
• 가지치기(Pruning): 해가 될 가능성이 없는 경우 해당 노드를 제외
• 백트래킹(Backtracking): 유망하지 않은 쪽으로 가지 않고 되돌아 옴

[!Note] 재귀함수와 BFS를 잘 활용하자!!

백트래킹 예시

1. N-Queen 문제

구현 코드

---

구현 코드

---

관련 문제

문제1. 백준[2839] 설탕 배달

작성 코드

---

문제2. 백준[1931] 회의실 배정

작성 코드

---