[알고리즘] 백트래킹 (Backtracking)

백트래킹 (backtracking) 이란?

• "가능한 모든 방법을 탐색한다"의 아이디어를 가진다.
• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 해를 다시 찾는 기법
• 가지치기(pruning)를 얼마나 잘하느냐에 따라 효율성이 결정되게 됨
  • 가지치기(pruning) : 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다.

DFS vs 백트래킹

• DFS
  • 가능한 모든 경로(후보)를 탐색
  • 불필요할 것 같은 경로를 사전에 차단하지 않으므로 경우의 수를 줄이지 못한다.
• 백트래킹
  • 가능한 모든 경로(후보) 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
  • 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.
  • DFS에 가지치기(pruning)를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법

문제 해결 방법

1. 상태 공간 트리의 깊이 우선 검색(DFS)을 실시함.
2. 각 노드가 유망한지(promising)를 점검
3. 해당 노드가 유망하지 않다면 부모로 돌아가서 검색을 계속함(Backtracking)

   해가 될 가능성이 있으면 유망하다(promising) 고 하며,
   유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 한다.

✔ 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.

예제) N과 M(1)

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

import sys
input = sys.stdin.readline

# 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
# 고른 수열은 오름차순
N, M = map(int, input().split())

s=[]

# 백트래킹 이용
def dfs():
  if len(s)==M:
    print(*s) # 공백으로 구분해서 출력
    return
  for i in range(1, N+1):
    # 중복 없게
    if i not in s:
      s.append(i)
      dfs()
      s.pop()

dfs()

1. s 리스트에 수열 저장
2. 리스트에 들어간 수열들이 m개가 되면 리스트 원소들을 모두 출력하고 함수 리턴
3. 1부터 N까지의 자연수 중 선택
   • 선택한 숫자를 다시 선택하려 하면(중복) 배제하는 방식으로 가지치기
   • 중복이 아니라면 해당 숫자를 s리스트에 추가하고, dfs() 호출, 동작이 끝난 후에는 s.pop() 수행