[BOJ] N-Queen (no.9663)

문제

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

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

입력

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

출력

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

🤔 생각

• 엇 체스룰 모르는데... 싶어서 찾아보니

• 대충 체스판에서 모든 퀸에 대해 상하좌우, 양대각선에 겹치는 퀸이 없어야 한다는 의미다.

• 위쪽 방향만 탐색하자. (세로, 양대각선 위방향)

📌 첫 풀이

# C++로는 가능, 파이썬으로 솔브 불가
import sys
input = sys.stdin.readline

n,ans = int(input()),0
grid  = [[False]*30 for _ in range(30)]

def check(x,y):
    for i in range(x+1):
        #print(x,y,i)
        if grid[i][y] or grid[x-i][y-i] or grid[x-i][y+i]: return False
    return True

def solve(x):
    global ans
    if x == n:
        ans += 1
        return

    for y in range(n):
        if check(x,y):
            grid[x][y] = True
            solve(x+1)
            grid[x][y] = False

solve(0)
print(ans)

오..되게 열심히 풀었는데 시간 초과로 솔브가 안 된다.
테스트 케이스 통과도 모두 확인했는데...

알고보니 동일 코드로 C++로 냈다면 솔브가 되는 것 같다.
물론 C++도 할 수는 있지만 파이썬이 주언어라 가끔 이런 문제를 보면 슬프다..

그럼 파이썬으론 아예 불가능한 문제인가 하면 그렇지도 않은 것 같다.
뭔가 더 최적화할 수 있는 묘수를 생각해내야 한다...

📌 최종 풀이

# PyPy3 로만 가능
import sys
input = sys.stdin.readline

n,ans = int(input()),0
a,b,c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve(x):
    global ans
    if x == n:
        ans += 1
        return

    for y in range(n):
        if not (a[y] or b[x+y] or c[x-y+n-1]):
            a[y] = b[x+y] = c[x-y+n-1] = True
            solve(x+1)
            a[y] = b[x+y] = c[x-y+n-1] = False

solve(0)
print(ans)

• 인덱스의 합차 규칙을 적용한 풀이다.

• 반복문으로 체스판을 매번 확인하지 않아도, 열과 대각선의 위치를 1차원으로 표현하기 때문에 시간복잡도가 훨씬 유리하다.

참고한 블로그

✔ 회고

• 백트래킹에서 바이블 격의 문제같긴 하지만
• 아직 어렵게 느껴진다..ㅠㅠ
• 연습하자 연습