[algo] 백트래킹(Backtracking)이란?
백트래킹 (Backtracking)
aka. 퇴각 검색 (Backtrack)
제약 조건 만족 문제에서 해를 찾기 위한 전략
해답이 될 수 있는 모든 벡터를 만들어 탐색하는 브루트포스는 시간과 공간의 복잡도가 증가하여 원하는 시간에 문제를 풀지 못하는 상황이 발생
해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법
실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현
각 후보를 DFS 방식으로 확인
상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
(위) 상태 공간 트리
Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)
대표적인 백트래킹 문제
N-Queen
https://velog.io/@letsbebrave/백준-9663-N-Queen
import sys
n = int(sys.stdin.readline())
mlist=[0]*n
def check(mlist, row): # Promising : 해당 행에 원소 배치해도 되는지 검사
for i in range(row):
if mlist[i] == mlist[row] or abs(mlist[row]-mlist[i]) == row - i:
return False # 방문할 수 없는 경우이므로 False 주기
return True
def search(mlist, row):
count = 0
if n == row:
return 1
for col in range(n):
mlist[row] = col
if check(mlist, row): # 퀸들이 이동할 수 없을 경우엔 다음 컬렴 (백트래킹)
count += search(mlist, row+1)
return count
print(search(mlist, 0))
출처
https://devlog-wjdrbs96.tistory.com/105
https://it00.tistory.com/26
Author And Source
이 문제에 관하여([algo] 백트래킹(Backtracking)이란?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@letsbebrave/algo-백트래킹Backtracking이란저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)