99클럽 코테 스터디2 -7일차(백트랙킹)

문제 : https://www.acmicpc.net/problem/17825

🚨 오늘의 학습

⭐️ 백트랙킹(BackTracking)⭐️

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

DFS와 백트래킹(BackTracking)

DFS(Depth-First Search)

• 깊이 우선 탐색으로 가능한 모든 경로를 탐색한다. (그래프에서 깊은 부분을 우선적으로 탐색)
• 모든 경로를 탐색하는 특징으로 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이진 못한다.

---

⭐️ 백트래킹(BackTraking) ⭐️

💡 백트래킹은 단순한 DFS가 아니라 "불필요한 탐색을 줄이는 기법" 이 추가된 탐색 방식

• 가능한 모든 경우를 탐색하지만 Sooooo 탐색 속도 개선↑

• 🔅 KEY POINT는 더 이상 탐색할 필요가 없는 상태를 제외한다는 것인데, 이를 가지치기라고 한다.

⛔️주의할점

🔹 핵심은 탐색 후 "이전 상태로 되돌리는것"이 백트래킹의 필수 요소!!

1. 방문 여부 체크 (visited 배열)
   → DFS 탐색 / 그래프 문제
2. 상태를 저장하는 배열이나 리스트 사용
   → N-Queen / 스도쿠 / 경로 찾기
3. 순열·조합 문제에서 선택한 값 되돌리기
   → 순열 생성 / 조합 찾기 / 부분 집합 문제

✅ [최적 상황]

1. 문제에서 "최적해를 찾는 것"보다 "가능한 해를 찾는 것"이 중요한 경우
2. 순열/조합
3. 정답이 하나가 아니라 여러 개일 수 있으며, 특정 조건을 만족하는 모든 해를 찾는 경우

---

🤔 4개의 말의 10번의 이동 순서 정하기 → (중복 순열---백트랙킹)

🤔 윷놀이판의 최단 경로 조건

1. 지름길(두가지 경로(blue/red)를 갖는다) : [10번] | [20번] | [30번]
2. [28] -> [30] -> [28(지름길)] | [32]
3. [18] -> [20] -> [22(지름길)]| [22]
4. [19] | [24] | [26] -> [25] ->[30]
5. 도착지점 : 40

🗝️
🗝️