[알고리즘] 백트래킹(backtracking) with 9663번 N-Queens - python

백트래킹(backtracking)

• 제약 조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 알고리즘
• 해에 대한 후보군을 점진적으로 구축하![]다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단 되는 즉시 후보를 포기(backtrack)한다.
• 이를(backtrack) 통해 계산의 양을 줄일 수 있다.

백트래킹 구현

• 실제 구현시 트리구조(상태공간트리(State Space Tree))를 이용하여 각 후보군을 표현한다.
• DFS(깊이 우선 탐색을)사용하여 각 후보군을 검사한다.
• 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다.
• 시도해보지 않은 다른 해결 방법이 있으면 시도한다.
• 해결 방법이 더 없으면
  문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이전의 분기점으로 돌아간다.

상태공간트리: 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

예시 N-Queens

• 백트레킹의 대표적인 예시인 N Queen 문제를 살펴보자
• NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
• 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 함(예시)
• 입력은 N이 주어지고, 출력은 N개의 퀸을 서로 공격 할 수 없게 놓는 모든 경우의 수
  

풀이

• 각 row 마다 위에서 아래로 부터 queen을 놓으며 조건을 만족하는를 판단한다.
• 해당 row에 Queen을 놓을 수 있는 자리가 있다면 queen을 두고 다음 row로 넘어간다.
• Queen을 놓을 수 없는 자리가 없다면 이전의 경우의 수로 돌아가 다른 경우의 수를 살핀다.
• 모든 row에 Queen을 다 두었다면 경우의 수에 1을 더한다.

전체 코드

N = int(input())
cnt = 0
def dfs(position_list, marks):
  # 가능한 경우의 수를 찾았다면 개수를 더한 후 재귀 종료
  if len(position_list) == N:
      global cnt;
      cnt += 1
      return None
  
  for col in range(N):
      if not marks[len(position_list)][col]:          
          for i, row in enumerate(range(len(position_list)+1, N)):
              marks[row][col] += 1 # colum을 체크하는 부분
              if col+(i+1) < N: # 대각선 오른쪽을 체크하는 부분
                  marks[row][col+i+1] += 1
              if col-(i+1) >= 0: # 대각선 왼쪽을 체크하는 부분
                  marks[row][col-(i+1)] += 1
          position_list.append(col)
          dfs(position_list, marks)
			
          # Backtracking 
          position_list.pop()
          for i, row in enumerate(range(len(position_list)+1, N)):
              marks[row][col] -= 1
              if col+(i+1) < N:
                  marks[row][col+i+1] -= 1
              if col-(i+1) >= 0:
                  marks[row][col-(i+1)] -= 1

marks = [[0] * N for _ in range(N)]
dfs([], marks)
print(cnt)

해설

marks = [[0] * N for _ in range(N)]

• N을 입력 받았을 때 퀸을 둘 수 있는 자리인지 아닌지를 마킹 하기 위하여 NxN리스트를 만들었다.

  for col in range(N):
      if not marks[len(position_list)][col]:          
          for i, row in enumerate(range(len(position_list)+1, N)):
              marks[row][col] += 1 # colum을 체크하는 부분
              if col+(i+1) < N: # 대각선 오른쪽을 체크하는 부분
                  marks[row][col+i+1] += 1
              if col-(i+1) >= 0: # 대각선 왼쪽을 체크하는 부분
                  marks[row][col-(i+1)] += 1
          position_list.append(col) # queen을 놓은 자리 저장
          dfs(position_list, marks) # 다음 row를 살펴본다

• position_list는 queen을 놓은 자리를 나타내는 값으로, 리스트의 각 값은 column의 index를, 해당 값의 index는 row index를 나타낸다. 예로 [1,2,3] 은 [0,1], [1,2], [2,3]의 자리에 queen을 둔 것을 의미한다.
• if not marks[len(position_list)][col]은 마킹이 되어 있지 않다면 queen 을 놓을 수 있는 자리라는 것을 의미한다. 해당 조건을 만족하면 queen을 두고 queen을 놓을 수 없는 자리에 마킹을 한다.
• queen을 놓는 방법은 위에서 아래로 두기 때문에, queen을 놓은뒤 우리가 신경써야 하는 부분은 해당 row의 아래영역만 신경쓰면된다. for i, row in enumerate(range(len(position_list)+1, N))
• queen을 두고 해당 자리의 아래 열, 오른쪽 아래 대각선 부분, 왼쪽 아래 대각선 부분에 마킹을 한다.
• position_list.append(col) 해당 자리에 queen을 두었다는것을 저장한다
• dfs(position_list, marks) 다음 경우의 수를 살핀다.

          # Backtracking 
          position_list.pop()
          for i, row in enumerate(range(len(position_list)+1, N)):
              marks[row][col] -= 1
              if col+(i+1) < N:
                  marks[row][col+i+1] -= 1
              if col-(i+1) >= 0:
                  marks[row][col-(i+1)] -= 1

• 앞서 탐색을 마친 후, 이전 경우의 수로 돌아가기 위해 Queen을 놓은 자리를 지우고 마킹도 지운다.

이미지 출처

• https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89
• https://en.wikipedia.org/wiki/Eight_queens_puzzle