반응형
백트래킹
여러개의 후보해 중에서 특정 조건을 만족시키는 모든 해를 찾는 알고리즘
ex_) 미로 탈출 알고리즘
- 갈림길->무조건 왼쪽
- 막다른 곳이 나오면 되돌아 나와서 오른쪽 시도
- 뿌리에서 해를 찾기 시작
- 현재 부분해에서 선택 가능한 다음 부분해 목록을 조회
- 부분해를 하나씩 하나씩 방문
- 해가 될 수 있는 조건이면 위를 다시 실행
- 아니면, 이전 부분해로 돌아나와서 다른 부분해를 실행
- 위의 단계를 반복
ex) 미로 탈출 찾기
- 재귀호출 기반 백트래킹
Algorithm/BackTracking at main · Sukmin-LanternK/Algorithm
Contribute to Sukmin-LanternK/Algorithm development by creating an account on GitHub.
github.com
반응형
'IT 공부 > 자료구조&알고리즘' 카테고리의 다른 글
| 알고리즘 12 동적계획법 (0) | 2025.03.26 |
|---|---|
| 알고리즘 11 분할 정복 (0) | 2025.03.22 |
| 알고리즘 10 알고리즘 성능 분석 (0) | 2025.03.19 |
| 알고리즘 9 문자열 탐색 (0) | 2025.03.18 |
| 알고리즘 8 그래프_3 (0) | 2025.03.10 |