[백준] N-Queens 문제(Python) - 백트래킹

# 문제 

즉, 상하좌우 대각선으로 이동하는 N개의 퀸을 서로 부딪히지 않도록 배열하는 방법 수를 리턴하는 문제이다. 백트래킹의 전형적인 문제 유형이라고 한다. 아래의 예시처럼 말을 놓는 경우의 수는 하나의 경우의 수가 될 것이다. 

 

# 입출력

 

# Idea

우선 해당 문제는 백트래킹 문제로, DFS 방법으로 문제를 푸는 방법을 고안할 수 있다. (백트래킹에 대해 궁금하신 분들은 여기를 참고!) 특히 이 문제를 처음 봤을 때, 나는 다음과 같이 DFS노드를 뻗으면 어떨지 생각을 했다. 각 raw별 좌표를 노드로 놓고, Depth는 raw 단위가 되도록 노드를 뻗는 것이다. 

특히 백트래킹은 유망한 노드(정답이 될 가능성이 있는 노드)이면 계속 DFS 탐색을 하고, 그렇지 않으면 탐색을 멈추고 위 depth의 노드로 돌아가는, 즉 효율을 추구하는 알고리즘 방법이다. 따라서 이 N-Queens 문제에서 "유망함" (즉 정답이 될 수 있는) 의 기준이란, 아마 Raw 단위로 탐색할 때 기존의 Queen의 위치와 상하좌우 대각선으로 만나지 않는 것일것이다. (그래야 정답이 될 수 있기 때문이다!) 

따라서 이 문제의 중요한 포인트는 "상하좌우 대각선에 해당 노드가 위치해있는지 체크하는 과정"이 존재해야 한다. 개인적으로 코드를 구현할 때 이 부분이 막막하게 느껴졌는데, 상하좌우 대각선을 체크하는 부분을 다음과 같이 구현할 수 있다. 

# 상하좌우 대각선 체크 함수
def check(n):
  for i in range(n):
    if (board[n] == board[i]) or (n-i == abs(board[n] - board[i])):    # 좌우에 있거나, 대각선에 있다면 
      return False 

  return True

위 코드에서 n은 특정 raw(=특정 depth)이다. 그리고 board에는 1차원 리스트로 해당 raw에서의 현재 queen의 위치가 적재된다. 
즉, 이 코드에서 board[n]이란 n번째 raw에서 현재 queen의 위치가 되는 것이다. 따라서 반복문을 통해 특정 raw의 좌표를 훑으면서, 현재 raw에서의 queen의 위치와 상하좌우 대각선에서 만나는지 검사하는 함수이다. 여기서 좌우와 대각선을 검사하는 방법은 다음 조건과 같다. (참고로 특정 raw의 노드들만 보는것이므로, 상하는 고려할 필요가 없다) 

• 좌우 검사 : 단순히 현재 queen의 column 위치와 기존에 적재된 queen 중 특정 queen의 column 위치가 같은지 확인하면 된다. 
  (board[n] == board[i] 부분) 
• 대각선 검사 : (현재 queen의 raw - 기존의 queen의 raw)가 |현재 queen의 column - 기존 queen의 column| 과 같은지 확인하면 된다. (n-i == abs(board[n] - board[i] 부분) 

 

 

# Code

위 아이디어를 코드로 구현하면 다음과 같다. board 1차원 리스트에는 raw별 queen이 적재되는 시스템이다. 즉, 아래와 같은 사진으로 이해하면 되겠다. 

"""
N queens 문제 
  - 내 최대 고민은 대각선, 가로세로 위치를 어떻게 확인할 것인가? (퀸 위치와 어떻게 비교할 것인가)
  - 대각선 조건 : (놓으려는 자리의 행 - 모든 행 중 하나) == abs(놓으려는 자리의 열 - 모든 행 중 하나의 열)
"""

def nqueen(depth):     
  global result
  
  # depth가 N일 때 > 모든 퀸을 다 놓은 것
  if depth == N : 
    result += 1 
    return 

  # depth별 반복문 
  for i in range(N):

    # 해당 depth를 visited 하지 않았을 때 
    if visited[i] == False : 
      board[depth] = i     # (depth, i)에 퀸 올리기 (여기서 depth는 raw, i는 column에 해당
      
      if check(depth):
        visited[i] = True
        nqueen(depth + 1)     # 그 다음 열로 넘어감 
        visited[i] = False    # 다시 false로 설정해 백트래킹 


# 모든 열에대해 퀸과 대각선, 좌우에 위치해 있는지 체크 
def check(n):
  for i in range(n):

    # 좌우에 있거나, 대각선에 있다면 
    # TODO(여기서 기존 queen이 어떻게 적재되고 있는걸까?)
    if (board[n] == board[i]) or (n-i == abs(board[n] - board[i])):
      return False

  return True

# main 
if __name__ == '__main__':
  N = int(input())    # dfs의 depth에 해당함 
  # depth별 적재 
  board = [0] * N     # 1차원 리스트로 적재 
  visited = [False] * N
  result = 0 

  nqueen(0)
  print(result)

 

참고로 위 코드 중에서 이 부분에서 백트래킹이 일어난다. visited를 다시 False로 설정하는 과정이다. 

  if check(depth):
    visited[i] = True
    nqueen(depth + 1)     # 그 다음 열로 넘어감 
    visited[i] = False    # 다시 false로 설정해 백트래킹