백트래킹 (Backtracking)

목차

백트래킹 (Backtracking)

• 백트래킹 알고리즘은 DFS의 한 형태로 깊이 탐색을 하다가 가능성이 없는 곳이면 빠르게 포기하고, 가능성이 있는 경로만을 따라 해를 찾아나가는 것입니다.
  • 즉, 가지치기 라고 할 수 도 있습니다.
• 백트래킹은 여러가지 예시를 살펴보면서 이해하는 것이 좋습니다.
• 대표적인 백트래킹 문제인 N-Queen
  • N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다.
  • 퀸은 상하좌우 어디로든 가고싶은만큼 이동할 수 있고,대각선으로도 원하는 만큼 이동할 수 있습니다.
  • https://www.cs.usfca.edu/~galles/visualization/RecQueens.html

예시

• [백준 9663] N-Queen
  • 현재 col기준으로 앞 col에 대해 같은 row에 있거나, 대각선에 있는 위치에 대해 체크를 진행해줍니다.
  • DFS로 탐색해서 들어갈때, board에 해당 값을 넣고 DFS로 탐색한뒤 해당 함수가 종료되고 해당 값을 다시 제거해줘야합니다. 그래야 올바르게 전체에대해서 탐색이 됩니다. (board[col] = row에서 함수 실행종료후, board[col] = -1로 다시 지정)
  • 코드

    • import sys
      
      input = sys.stdin.readline
      
      n = int(input())
      
      board = [-1 for _ in range(n)]
      answer = 0
      
      
      def is_safe(row, col):
          for i in range(col):
              # 앞 col의 row랑 같은 row에 존재하는경우 or 앞 col에서 같은 대각선에 존재하는경우(row-이전row = col-이전col)
              if board[i] == row or (abs(board[i] - row) == abs(i - col)):
                  return False
          return True
      
      
      def n_queen(col):
          global answer
          if col == n:
              answer += 1
              return
      
          for row in range(n):
              if is_safe(row, col):  # 현재 위치에 퀸삽입가능
                  board[col] = row
                  n_queen(col + 1)  # 다음 col 체크 진입
                  board[col] = -1  # 다시 현재 col에서 다음 row에 대해 체크해봐야함.
      
      
      n_queen(0)
      print(answer)