[백준/BOJ][Python] ⭐9663번 N-Queen

9663번 N-Queen

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

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1

92

---

풀이

N과 M시리즈를 풀면서 백트래킹을 공부하다가 문제 풀이 방법이 신기해서 풀게 됐다.

우선 퀸이 같은 열에 위치하면 안되고 대각선으로 위치해도 안된다.
1) 같은 열인지 확인

• Y가 같은지 확인하면 됨

2) 왼쪽 대각선에 있는지 확인

• x가 1 감소하면 y가 1 증가하므로 X+Y가 같다.
• (1,1) 기준으로 왼쪽 대각선은 (0, 2) 백트래킹이므로 위는 생각 안하고 밑만 생각하면 된다.

3) 오른쪽 대각선에 있는지 확인

• X-Y가 같다.
• (1,1) 기준으로 오른쪽 대각선은 (2, 2), (3, 3)

이 세가지 경우만 따로 배열 만들어서 처리하면 된다.

출처 : 바킹독님

접근 방법이 신기해서 나중에 다시 한 번 풀어봐야겠다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
isUsed1 = [False]*n # 열
isUsed2 = [False]*(n+n-1) # 왼쪽 아래로 대각선
isUsed3 = [False]*(n+n-1) # 오른쪽 아래로 대각선
cnt = 0

def back(cur):
    global cnt
    if cur == n:
        cnt += 1
        return

    for i in range(n):
        if isUsed1[i] or isUsed2[i+cur] or isUsed3[cur - i + n - 1]: continue
        
        isUsed1[i] = True
        isUsed2[cur+i] = True
        isUsed3[cur-i+n-1] = True
        back(cur+1)
        isUsed1[i] = False
        isUsed2[cur + i] = False
        isUsed3[cur - i + n - 1] = False

back(0)
print(cnt)