[Python] 백준 9663번 : N-Queen

9663번: N-Queen

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

---

✔ Solution - PyPy3 소스코드

n, ans = int(input()), 0
a, b, c = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)  # a=수직, b=우상향대각선, c=좌상향대각선의 각각 가능한 칸수만큼


def solve(i):
    global ans
    if i == n:  # 퀸을 다 놓았다면
        ans += 1  # 경우의 수를 한개 추가
        return  # 종료
    for j in range(n):  # 열을 이동하면서
        if not (a[j] or b[i + j] or
                c[i - j + n - 1]):  # 인덱스의 합과 차가 같다는 것을 이용, 세가지 조건에 부합하지 않는다면
            a[j] = b[i + j] = c[i - j + n - 1] = True  # True 표시
            solve(i + 1)  # 다음 퀸을 놓기 위해 재귀.
            a[j] = b[i + j] = c[i - j + n - 1] = False  # 초기화


solve(0)
print(ans)

 

# 문제 포인트

• 가능 여부를 확인할 때, 하나의 배열에서 매번 상하좌우 대각선을 확인하는 것은 효율적이지 않다.
• 3개의 배열을 만들고, 각각 세로 줄(|), 대각선 줄(/), 대각선 줄(\)을 체크한다.
• N x N 판에서 한 칸의 인덱스를 [X, Y]라 하자. 세로 줄(|)은 각 칸이 [Y]이며, 대각선(/)은 각 칸이 [X+Y]이고, 대각선(\)은 각 칸이 [X-Y+N-1]이다. 아래의 그림은 N이 5일 때의 예시다.
• solve 함수에서 인자 i는 행(row)이며, for 문의 j는 열(column)을 나타낸다. 즉, 가장 위 행에서 아래 행으로 순서대로 내려가면서, for 문과 if 문을 통해 어떤 열에 놓을지 결정하는 것이다.

출처: https://rebas.kr/761 [PROJECT REBAS]