백준 22.01.28. 9663번 - N-Queen

def N_Queen(idx):
    if idx == N:
        global result
        result += 1
        return
    else:
        for i in range(N):
            queen[idx] = i
            if Promise(idx):
                N_Queen(idx + 1)


def Promise(idx):
    for i in range(idx):
        if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
            return False
    return True


N = int(input())
queen = [0] * N
result = 0
N_Queen(0)
print(result)

• python3는 시간초과에 걸린다는 글이 많아서 pypy3로 제출하여 통과했습니다

 N Queen - 위키백과

• 우선 queen리스트를 입력받은 N만큼의 길이인 1차원 배열을 만들어줍니다.
• 체스판은 2차원배열인데 1차원배열로 만드는 이유는 인덱스와 값이 각각 x, y좌표역할을 하기때문입니다.
  •  ex) (1,6)에 퀸이 있다면 queen[1] = 6인 방식입니다.
  • 위 코드에서는 (0,0)이 왼쪽 맨 윗칸의 좌표로 기준을 잡고 작성했습니다.
• 체스에서의 퀸은 대각선, 직선으로 움직일 수 있습니다.
  • 따라서 퀸이 있는 행, 열, 대각선에는 또 다른 퀸이 있을 수 없습니다.
• 그렇기 때문에 queen리스트의 각 인덱스는 값을 1개씩만 가지는 형태로 충분합니다.

• queen[0] = 0일 때, queen[1]의 값은 2,3,4가 될 수 있습니다.
• 코드에 따라 차례대로 진행하여 queen[1] = 2일 때 퀸이 들어갈 수 있는 남은 칸은 오른쪽 그림과 같습니다.

• 이어서 세번째 줄에 퀸을 할당해주고 네번째 줄에도 퀸을 할당해주면 다섯째 줄에 퀸이 들어갈 자리가 남습니다.
• 이런식으로 진행하여 이전 퀸들의 행,열,대각선을 모두 탐색하여 들어가 자리가 있는지 탐색하는 방식입니다.
• 만약 다음줄에 들어갈 자리가 없다면(Promise 함수가 모두 False라면) 해당 위치에 퀸을 뒀을때는 해가 없는 것이므로 다음 반복문을 통해 탐색을 진행합니다.

• if idx == N:
          global result
          result += 1
          return

  N_Queen의 해당 부분은 4째줄의 퀸을 두었는데 5번째 줄에 둘 칸이 있으면 해가 있는 것이므로 result를 +1 해주는 코드입니다. 
  • 앞서 말했듯이 행,열,대각선이 모두 겹치면 안되므로 마지막 줄까지 둘 칸이 남아있다면 남은 칸의 수는 1개일 것입니다.

•     	for i in range(N):
              queen[idx] = i
              if Promise(idx):
                  N_Queen(idx + 1)
                  
  def Promise(idx):
      for i in range(idx):
          if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
              return False
      return True

• 그리고 DFS코드를 보자면 for문을 통해 해당 열(row)의 경우의 수를 모두 탐색하며 해당 칸에 퀸을 위치했을 때, 그 위치가 이전에 둔 퀸들의 행,열,대각선에 걸리지 않는지 여부를 Promise함수로 판단합니다.
• 조건에 부합하는 위치가 있다면 True가 반환되며 재귀를 통해 그 다음 열에서 해를 탐색합니다.