backtrackingdfspruning

Backtracking을 설명해 주세요

예상 시간
6분
30초 답변

꼬리질문

조금 더 깊게 물어본다면

답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.

Pruning이 없으면 어떻게 되나요?

부가 설명

완전 탐색과의 차이는 가지치기입니다. 완전 탐색은 모든 경로를 끝까지 가보지만, backtracking은 현재 경로가 답이 될 수 없다고 판단되는 순간 즉시 되돌아가 다음 선택을 시도합니다.

구현에서 핵심은 상태 복구입니다. 선택 전후 상태가 동일해야 다른 경로를 올바르게 탐색할 수 있습니다.

function backtrack(상태):
  if 완료 조건:
    결과에 추가
    return
  for 각 선택지:
    if 유효하지 않으면 skip   // 가지치기
    상태 변경                // 선택
    backtrack(다음 상태)
    상태 복구                // 취소

순열과 조합의 구현 차이는 방문 처리 방식에 있습니다. 순열은 visited 배열로 이미 쓴 원소를 제외하고, 조합은 시작 인덱스를 앞으로 밀어 이전 원소를 다시 선택하지 않습니다.

한 줄 정리

Backtracking은 DFS 탐색에 가지치기를 더해 불가능한 경로를 조기에 차단하는 기법입니다.