[백준] 9663번 N-queen _ python

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

1차 시도 - python3으로 시간 초과, pypy3으로 성공

import sys
sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())
result = 0
chess = [0] * n

def check(x):
    for j in range(x):
        if chess[x] == chess[j] or x - j == abs(chess[x] - chess[j]):
            return False
    return True

def nqueen(r):
    global result

    if r == n:
        result += 1
    else:
        for i in range(n):
            chess[r] = i
            if check(r):
                nqueen(r+1)

nqueen(0)
print(result)

어려웠던 점

1. 대각선을 어떻게 처리해주나?

• 대각선의 경우 가로 세로 이동량이 같다는 게 포인트.
• 따라서 행-행 == |열-열| 이 같다는 것을 활용

2. 이차원 배열 사용? 못 가는 곳을 따로 체크해주는 배열이 필요할까?

• 1차원 배열로도 해결 가능
• list에서 index가 행, chess[index]가 열으로 구성
• 못 가는 곳을 따로 체크해주는 배열을 만들면 재귀 돌릴 때마다 처리가 힘들기 때문에 그럴 필요 없음.
• 그냥 for문으로 n번 돌리면서 다 확인해주는 게 낫다.

2차 시도 - python3으로 시간 초과, pypy3으로 성공

check 함수를 거치기 전에, 미리 앞에서 거쳤던 열은 그냥 패스하도록 조건 걸어둠.
python3에서는 여전히 시간 초과.. pypy3에서는 그래도 시간이 훨씬 줄어듦. 29372ms -> 16484ms

import sys
sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())
result = 0
chess = [-1] * n

def check(x):
    for j in range(x):
        if x - j == abs(chess[x] - chess[j]):
            return False
    return True

def nqueen(r):
    global result

    if r == n:
        result += 1
    else:
        for i in range(n):
            if i in chess:	# 앞서 지나갔던 열은 미리 그냥 지나가도록 함.
                continue
            chess[r] = i
            if check(r):
                nqueen(r+1)
            chess[r] = -1	# 다시 안 씀 처리 해줘야 함.
nqueen(0)
print(result)