[Beakjoon] 9663. N-Queen

🔗 Problem Link

https://www.acmicpc.net/problem/9663

---

❔Thinking

• 체스판의 퀸의 이동경로가 겹치지 않도록 N개를 놓는 방법의 수를 구한다.
• 퀸은 상하좌우, 대각선 모두를 이동할 수 있다.

---

💻Solution

n = int(input())

def put_queen(row:int):
    global left_right, yx, y_x, cnt, n
    if row == n:
        cnt += 1
        return
    for i in range(n):
        if left_right[i] is False and yx[row+i] is False and y_x[(n-1) + row-i] is False:
            left_right[i] = True
            yx[row+i] = True
            y_x[(n-1)+row-i] = True
            put_queen(row+1) 
            left_right[i] = False
            yx[row+i] = False
            y_x[(n-1)+row-i] = False


left_right = [False] * n
yx = [False] * (2*(n-1)+1)
y_x = [False] * (2*(n-1)+1)
cnt = 0
put_queen(0)
print(cnt)

---

🗝️keypoint

1. 상하좌우, 왼쪽 대각선, 오른쪽 대각선 이렇게 3가지로 나누어 생각할 수 있다.
   1. 상하좌우 : 1차원 배열을 정의하고, 배열의 인덱스를 열의 번호라 생각한다.
   2. 왼쪽 대각선 : y = x인 함수와 같다고 생각하고, 이 대각선의 모든 위치는 "행 + 열" 이 같다 ((4,0) = (3,1)
   3. 오른쪽 대각선 : y = -x인 함수와 같다고 생각하고, 이 대각선의 모든 위치는 "행 - 열"이 같다 ((2,1) = (1,0))
2. N의 최대가 12이기 때문에, 모든 경우의 수를 파악하는 방법은 시간초과가 발생한다.