[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차원으로 표현하기 때문에 시간복잡도가 훨씬 유리하다.
✔ 회고
- 백트래킹에서 바이블 격의 문제같긴 하지만
- 아직 어렵게 느껴진다..ㅠㅠ
- 연습하자 연습
Author And Source
이 문제에 관하여([BOJ] N-Queen (no.9663)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wisepine/BOJ-N-Queen-no.9663저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)