백트래킹

해를 찾는 도중 해가 아니어서 막히면, 돌아가서 다시 해를 찾아가는 기법이다. 브루트포스로 가능할 것 같은데 경우의 수가 많아 시간초과가 날 것 같다면 백트래킹 확률이 높다. 최적화 문제와 결정 문제를 풀때 유용하다. '막히면 다시 돌아간다'라는 말이 처음엔 와닿지 않을 수 있지만 아래 그림처럼 재귀함수 호출 전에 했던 조건을 원래대로 돌리는 코드가 그중 하나이다. 원래 False였던 visited의 값을 True로 한 경우의 상황이 재귀함수A호출의 세계이고, visited의 값을 False로 되돌렸을 때의 세계는 따로 존재하게 되는 것이다.
(그림으로 밑에나올 예제들을 일반화시켜 간략히 표현했다.백트래킹문제가 전부 이렇진 않다.밑에 나올 예제들은 대략 이런게 반복된다고 생각하고 넘어가자)

유망성 판단

백트래킹은 모든 경우의 수를 판단하는 dfs와 다른 점이 바로 유망성 판단이다. 조건문으로 답이 될수없는 or 있는 상황을 정의하고 탐색을 계속할 것인지(재귀함수 호출 등), 그 이전상황의 상태로 돌아가서 다른 경우를 탐색할 것인지 구현하는 부분이다.

예제1.N과M(9)

#15663번
n, m = map(int, input().split())
nums = sorted(list(map(int, input().split())))
visited = [False] * n
temp = []

def backtracking():
    if len(temp) == m:
        print(*temp)
        return

    remember_me = 0
    for i in range(n):
        if not visited[i] and remember_me != nums[i]:
            visited[i] = True
            temp.append(nums[i])
            remember_me = nums[i]
            backtracking()
            visited[i] = False
            temp.pop()

backtracking()

예제2. 백준 암호만들기

#1759번
l,c = map(int,input().split())
alphabets = list(map(str,input().split()))
alphabets.sort()
moeum = ['a','e','i','o','u']
tmp = []
visited = [False for _ in range(c)]

def backtracking(depth, isMoeumExist, prevIdx, jaeumCnt):
   if depth == l and isMoeumExist and jaeumCnt >= 2:
      print(''.join(tmp))
      return
   previousIdx = prevIdx
   for i,v in enumerate(alphabets):
      if previousIdx < i and not visited[i]:
         tmp.append(v)
         visited[i] = True
         if v in moeum:
            backtracking(depth + 1, True, i, jaeumCnt)
         else:
            backtracking(depth + 1, isMoeumExist, i, jaeumCnt + 1)
         visited[i] = False
         tmp.pop()

backtracking(0, False, -1, 0)

예제3.N과M(3)

#15651번
n,m = map(int,input().split())
l = [i+1 for i in range(n)]
answer = []
arr = []
def backtracking(depth,numbers):
   tmp = [tv for ti,tv in enumerate(numbers)]
   if depth == m:
      answer.append(tmp)
      return

   for li,lv in enumerate(l):
      tmp.append(lv)
      backtracking(depth+1, tmp)
      tmp.pop()

backtracking(0,arr)

for idx,items in enumerate(answer):
   for _,item in enumerate(items):
      print(item, end=' ')
   print()

예제4.월드컵

from itertools import combinations

def dfs(depth):
   global cnt
   #15번째 경기에 도달했을 때
   if depth == 15:
      cnt = 1
      for sub in res:
         #승무패가 모두 소거되지 못해서 0이 3개가 아니면
         if sub.count(0) != 3:
            cnt = 0 #불가능한 예제
            break
      return

   #전체 경기 15번의 조합
   g1,g2 = games[depth]
   #각 경기의 승무패
   for x,y in ((0,2), (1,1), (2,0)):
      if res[g1][x] > 0 and res[g2][y] > 0:
         res[g1][x] -= 1
         res[g2][y] -= 1
         dfs(depth+1)
         # 백트래킹 특유의 작업 후 재귀돌리고 원상복구
         res[g1][x] += 1
         res[g2][y] += 1

l = []
answer = []
games = list(combinations(range(6),2))

for _ in range(4):
   tmp = list(map(int, input().split()))
   res = [tmp[i:i+3] for i in range(0,16,3)]
   cnt = 0
   dfs(0)
   answer.append(cnt)

print(*answer)