백준 9663번 [Python] 문제풀이 (N-Queen) - 이정개

문제

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

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

 

입력

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

 

 

출력

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

 

 

예제 입력 1

8

 

 

예제 출력 1

92

 

 

알고리즘 분류

ㆍ백트레킹

 

 

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)


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

한동한 나를 알고리즘 문제에서 도망치게 한 문제.

지금까지의 백트레킹은 어떻게든 해내왔으나

시간초과와 대각선 구현 문제로 하루종일 끙끙대다 결국 GG.

 

정답을 찾아보니 느려터진 파이썬은

시간제한을 극복하면서 코드를 구하는게 꽤 어려운 듯.

제출도 Python3이 아닌 PyPy3으로 해야 시간초과가 나지 않는다.

그러다보니 난이도가 비약적으로 상승한게 없지않아 있다.

 

결론 : 인덱스의 합이 같은 경우 같은 대각선 상에 위치함을 참고할 것.

https://rebas.kr/761