백트래킹 - 바킹독 유튜브를 보고

개념

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

선택지가 주어지는 게임을 예로 들면 선택지 별로 결과가 달라진다고 하면 돌아가서 두번째, 세번째 선택지를 다시 선택해볼 것이다. 이런식으로 모든 경우를 다 훑어보게 된다.

상당한 구현력을 필요로하고 실수하기도 쉽다. 그리고 재귀의 특성상 실수한 부분을 찾기가 어렵다. 많은 연습시간을 할애하지 않으면 대충 풀이는 알겠으나 코드로 옮기지 못해 문제를 틀릴 확률이 높다.

다행인점은 응용을 할 수 있는 건덕지가 많지 않기 때문에 예제들을 꼼꼼히 풀면서 익숙해지면 그럭저럭 할 만 하다.

연습문제

• boj-15649 백트래킹은 상태를 넘나든다. 배열이 빈 상태, 1이 들어있는 상태 등

  N, M = map(int, input().split())
  def backtracking(n):
      if n == 0:
          print(" ".join(map(str,answer)))
          return
  # 이 부분이 백트래킹의 핵심이면서 재귀에 익숙하다고 해도 헷갈릴 파트이다.
  # 이해가 안가는 부분이 있다면 answer, n등을 프린트해보며 어떻게 변하는지 볼 필요가 있다.
      for i in range(1, N+1):
          if i not in answer:
              answer.append(i)
              backtracking(n-1)
              answer.pop()
  # 
  answer = []
  backtracking(M)
  
  # is_used를 사용하여 풀어보기
  def backtracking(n):
      if n == M:
          print(*answer[:M])
          return
      for i in range(1, N+1):
          if not is_used[i]:
              answer[n] = i
              is_used[i] = True
              backtracking(n+1)
              is_used[i] = False
              
  N, M = map(int, input().split())
  answer = [0]* 10
  is_used = [False] * 10
  backtracking(0)

• boj-9663 같은 행, 열 대각선에 퀸을 놓을 수 없기 때문에 이전에 is_used를 통해 검사했던 것과 마찬가지로 미리 값을 넣어놓으면 일일히 검사할 필요없이 시간을 줄일 수 있다. 어떻게 검사할 수 있을까? 좌측 하단과 우측 상단을 잇는 대각선은 x+y의 값이 일치한다. 예를 들어 0,1 과 1,0은 대각선 상에 존재하고 0+1 , 1+0은 1로 같다. 반대로 좌측 상단과 우측하단을 잇는 대각선은 x-y의 값이 일치한다. 0, 0 과 1, 1 은 동일한 대각선상에 있고 0-0 , 1-1 은 0으로 같다.

  N = int(input())
  chess_map = [[0] * N for _ in range(N)]
  col = [False] * N
  dial1 = [False] * (N * 2)
  dial2 = [False] * (N * 2)
  answer = 0
  def n_queen(n):
      global answer
      if n == N:
          answer +=1
          return
      for i in range(N):
  				# 행은 n의 반복을 통해서 확인을 하고 있고
  				# 지금 순회하고 있는 for문을 통해 확인할 수 있다.
  				# 그렇기 때문에 지금 인덱스 i가 열 c에 대응되고
  				# x+y 가 n+1, x-y가 n-1에 대응된다.
  				# 각 배열의 값들이 하나라도 true라면 퀸을 놓아볼 필요도 없다.
  				# 이런식으로 조건으로 거르는 상황을 가지치기라고 한다.
          c, d1, d2 = i, n+i, n-i+N-1
          if col[c] or dial1[d1] or dial2[d2]: continue
          col[c] = dial1[d1] = dial2[d2] = True
          n_queen(n+1)
          col[c] = dial1[d1] = dial2[d2] = False
          
  n_queen(0)
  print(answer)

• boj-1182 부분집합을 고르는 경우의 수는 2n 개 이다. 공집합을 빼고 생각해보면 2n -1개의 부분집합을 가지고 이 부분집합들을 다 더해보고 이 합이 S와 일치하는지 검사하면 된다. 지금 인덱스 cur인덱스에 있는 값을 더하거나 더하지 않거나 두가지 상황을 다 재귀함수에 담아 계산해주면 된다. 마지막 0일때 -1은 크기가 양수인 부분수열만 센다고 했기 때문에 공집합을 제외시켜주어야 한다.

  N, S = map(int, input().split())
  numbers = list(map(int, input().split()))
  answer = 0
  
  def backtracking(cur, cur_sum):
      global answer
      
      if cur == N:
          if cur_sum == S:
              answer +=1
          return
      
      backtracking(cur+1, cur_sum)
      
      backtracking(cur+1, cur_sum + numbers[cur])
  
  backtracking(0, 0)
  
  if S == 0:
      answer -=1
  print(answer)

피드백

이제까지 collections나 itertools 사용하는 것을 좀 꺼려왔는데 그럴 필요가 전혀 없을 것 같다. 굳이 시간을 들여서 백트래킹으로 순열 조합을 구할 시간에 도구를 잘 활용해서 빠르게 문제를 푸는 데에만 집중하자.