"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 12장의 써머리입니다."

12. 백트래킹(Back Tracking)

1) 백트래킹과 백트래킹 알고리즘

백트래킹이란?

어떤 가능성이 없는 곳을 알아보고 되돌아가는 것

백트래킹 알고리즘이란?

가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘 → 문제마다 효율 다름

답을 찾는 과정에서 가능성이 없는 곳에서 백트래킹

백트래킹을 통해 가능성 없는 탐색 대상 배제 가능하여 탐색 효율이 완전 탐색보다는 좋음

유망 함수란?

백트래킹 알고리즘의 핵심, ‘해가 될 가능성을 판단하는 것’
→ 그 가능성은 유망 함수라는 것을 정의하여 판단

* 백트래킹 알고리즘 과정

1. 유효한 해의 집합 정의
2. 위 단계에서 정의한 집합을 그래프로 표현
3. 유망 함수 정의 → 특정 조건을 정의하는 것 eg) 처음에 뽑은 숫자가 3 미만이면 백트래킹
4. 백트래킹 알고리즘을 활용하여 해를 찾음
   
   

2) 몸 풀기 문제

문제 47) 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기

정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환
제약 조건 - 숫자 조합은 오름차순, 같은 숫자는 한 번만 선택 가능

def solution(n):
  res = []
  
  def bt(n, start, tot, cur_sum, cur, res):
    if cur_sum == tot:
      res.append(cur.copy())
      return res
    
    for i in range(start, n+1):
      if cur_sum + i <= tot:
        cur.append(i)
        cur_sum += i
        
        bt(n, i+1, tot, cur_sum, cur, res)
        
        cur.pop()
        cur_sum -= i
      
  bt(n, 1, 10, 0, [], res)
  
  return res

assert solution(5) == [[1, 2, 3, 4], [1, 4, 5], [2, 3, 5]]
assert solution(2) == []
assert solution(7) == [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5],[2, 3, 5], [3, 7], [4, 6]]

문제 48) 스도쿠 퍼즐

9 x 9 스도쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 함수 작성
해는 유일하지 않을 수 있음
규칙 1) 가로줄, 세로줄에는 1부터 9까지의 숫자가 한 번씩 나타나야 함
규칙 2) 9 x 9 보드를 채울 9개의 작은 박스에도 1부터 9까지 숫자가 한 번씩 나타나야 함

def solution(board):

  def is_valid(row_val, col_val, num):
    return not (in_row(num, row_val) or in_col(num, col_val) or in_box(num, row_val, col_val))
  
  def in_row(num, row_val):
    return num in board[row_val]
  
  def in_col(num, col_val):
    for i in range(len(board)):
      if board[i][col_val] == num:
        return True
    
    return False
  
  def in_box(num, row_val, col_val):
    start_row = row_val - row_val % 3
    start_col = col_val - col_val % 3
    
    for i in range(3):
      for j in range(3):
        if board[start_row + i][start_col + j] == num:
          return True
        
    return False
  
  def find_empty():
    for i in range(len(board)):
      for j in range(len(board[i])):
        if board[i][j] == 0:
          return (i, j)
        
    return None
  
  empty_loc = find_empty()
  if not empty_loc:
    return board
  row, col = empty_loc
  
  for num in range(1, 10):
    if is_valid(row, col, num):
      board[row][col] = num
      if solution(board):
        return board
      board[row][col] = 0
      
  return False

assert solution([
	[5, 3, 0, 0, 7, 0, 0, 0, 0],
	[6, 0, 0, 1, 9, 5, 0, 0, 0],
	[0, 9, 8, 0, 0, 0, 0, 6, 0],
	[8, 0, 0, 0, 6, 0, 0, 0, 3],
	[4, 0, 0, 8, 0, 3, 0, 0, 1],
	[7, 0, 0, 0, 2, 0, 0, 0, 6],
	[0, 6, 0, 0, 0, 0, 2, 8, 0],
	[0, 0, 0, 4, 1, 9, 0, 0, 5],
	[0, 0, 0, 0, 8, 0, 0, 7, 9],
]) == [
	[5, 3, 4, 6, 7, 8, 9, 1, 2],
	[6, 7, 2, 1, 9, 5, 3, 4, 8],
	[1, 9, 8, 3, 4, 2, 5, 6, 7],
	[8, 5, 9, 7, 6, 1, 4, 2, 3],
	[4, 2, 6, 8, 5, 3, 7, 9, 1],
	[7, 1, 3, 9, 2, 4, 8, 5, 6],
	[9, 6, 1, 5, 3, 7, 2, 8, 4],
	[2, 8, 7, 4, 1, 9, 6, 3, 5],
	[3, 4, 5, 2, 8, 6, 1, 7, 9],
]

3) 합격자가 되는 모의 테스트

문제 49) 피로도

유저의 현재 피로도 k와 각 던전 별 최소 필요 피로도, 소모 피로도가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때 유저가 탐험할 수 있는 최대 던전 수를 반환하는 함수 작성

def solution(k, dungeons):
  visited = [False] * len(dungeons)
  
  def explore(k, visited):
    dun_count = 0
    
    for i in range(len(dungeons)):
      if not visited[i] and dungeons[i][0] <= k:
        visited[i] = True
        dun_count = max(dun_count, 1 + explore(k - dungeons[i][1], visited))
        visited[i] = False
    
    return dun_count
  
  return explore(k, visited)

assert solution(80, [[80, 20], [50, 40], [30, 10]]) == 3