[Algorithm] 3. 백트래킹

정의

이름 그대로, 해를 찾는 과정에서 막히면 처음으로 돌아가는 방법이다. (= 가지치기)

재귀를 이용한 완전 검색을 하고 가지치기를 추가하는 기법

결론적으로, 불필요한 계산낭비를 방지하는 방식이라고 생각하면 된다.

 

주로 최적화문제와 결정문제를 해결하는데에 사용된다.

ex_ 미로찾기, n-Queen 문제, Map coloring, 부분집합의 합 문제

 

코드 예시

N, M = map(int, input().split())
ans = []

def back():
    if len(ans) == M: # 배열의 길이를 확인
        print(" ".join(map(str, ans))) # 1 2 3 이런 상태로 출력하기 위해
        return 
    for i in range(1, N+1): # 1 ~ N 까지
        if i not in ans: # 중복 확인
            ans.append(i) # 배열 추가
            back() # 재귀
            ans.pop() # return으로 돌아오면 이게 실행됨. 1, 2, 3 일때 3을 없앰으로 전 단계로 돌아가는 것
            
back()

 

백준 백트래킹 문제 풀이

GitHub - HoonT/TIL: problem-solving