백트래킹
참고 자료
백준 관련 문제
‘백트래킹’이란
- 한정 조건을 가진 문제를 푸는 전략으로 모든 경우의 수를 시도해 문제의 정답을 찾아감
- 원리
- 각 단계에서 해결책 후보근 중 하나를 선택하고 이 선택이 조건을 만족하는지 검사
- 조건을 만족하지 않으면 이전 단계로 돌아가 다른 후보군 선택
- 1,2 과정을 반복하면서 최종적으로 해결책을 찾아가는 것이 백트래킹의 기본적인 원리
코드 형
def 재귀함수(n):
if 정답 :
출력 or 저장
else : # 정답이 아니면
for 모든 자식 노드에 대해서:
if 정답 가능성이 있으면:
자식노드로 이동
재귀함수(n+1)
부모노드로 이동