[Algorithm] 백트래킹

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다.

DFS와 백트래킹

1. 깊이 우선 탐색 (DFS) - 완전 탐색 방법

   • DFS는 가능한 모든 경로를 탐색하는 방식으로 불필요할 것 같은 경로를 사전에 차단하는 등의 행동이 없기 때문에 경우의 수를 줄이지 못 한다.
   • 따라서, N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능하다!

2. 백트래킹 (Backtracking)
   • 해를 찾아가는 도중, 현재 경로가 해가 될 것 같지 않으면 그 경로를 더이상 탐색하지 않고 되돌아간다. (이를 가지치기라고 함)
   • 코딩에서 반복문의 횟수를 줄일 수 있으므로 효율적이다.
   • 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
   • ❗주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.❗

백트래킹 입문 예제

BOJ #15649번 : N과 M (1)

문제 풀이

import sys

n, m = map(int, sys.stdin.readline().split())

s = []

def f():
  if len(s) == m:
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    if i in s:  # 가지치기?
      continue
    s.append(i)
    f()
    s.pop()

f()

• for 문으로 1부터 N까지 돌리면서 이미 선택한 값이 아닌 경우 선택 : 가지치기

if len(s) == m:
    print(' '.join(map(str, s)))
    return

또 다른 풀이는 파이썬의 in 연산자를 사용하는 것이 아니라 visited 리스트를 사용한다.

• 코드 간결성 : in 연산자를 사용하는 것이 코드가 더 간결함
• 시간 복잡도 : in 연산자가 O(n)의 시간복잡도를 갖기 때문에 visited 리스트를 사용하는 것이 더 효율적
• 공간복잡도 : in 연산자를 사용하는 코드가 리스트를 visited 리스트를 사용하지 않기 때문에 더 효율적