#백트래킹

현재 선택을 확장하고, 조건에 맞지 않는 후보는 제외하며 가능한 답을 생성하는 문제를 다룬다. 현재 4개의 풀이가 있다.

백트래킹 학습 가이드

필요한 주제만 펼쳐서 후보를 만들고, 조건에 따라 탐색을 줄이며 상태를 복원하는 방법을 익힌다.

후보를 하나씩 선택하는 탐색

백트래킹은 현재 상태에서 다음 후보를 하나 선택하고, 그 선택으로 만들 수 있는 상태를 더 탐색하는 방법이다. 완성된 답에 도달하면 결과에 저장하고, 재귀에서 돌아오면 선택을 취소해 다음 후보를 살펴본다.

유효한 접두 상태와 가지치기

완성된 답만 검사하는 대신, 현재 접두 상태가 이미 조건을 어겼다면 그 아래의 후보를 만들지 않는다. Generate Parentheses에서는 닫는 괄호 수가 여는 괄호 수를 넘는 순간 유효한 문자열로 이어질 수 없다.

if open_count < n:
    # 여는 괄호를 더 선택할 수 있음
if close_count < open_count:
    # 짝이 맞지 않은 여는 괄호가 있을 때만 닫기

문제마다 유효성 규칙은 다르지만, “현재 선택이 이미 목표를 불가능하게 만들었는가?”를 확인하면 탐색 전에 안전하게 후보를 제외할 수 있다.

선택과 복원 순서

공유하는 `path`에 후보를 추가하고 재귀 호출한 뒤, 돌아오면 마지막 후보를 제거한다. 각 호출이 시작될 때 `path`는 그 호출의 선택 상태와 정확히 일치해야 한다.

path.append(candidate)
search(next_state)
path.pop()

결과 목록에 현재 경로를 저장할 때는 `path.copy()`처럼 복사해야 한다. 같은 가변 리스트를 그대로 저장하면 이후 선택과 복원 과정에서 이미 저장한 답도 바뀐다.

자주 하는 실수