공부일지 210703

백준 9663번 문제를 풀었다. N-queen 문제였는데 시간제한 문제로 파이썬으로 푸는 것은 별로 추천하지 않는다는 이야기가 있었다. 이런저런 자료를 참고하면서 코드를 정리해봤지만 PyPy3으로 채점해도 겨우겨우 정답처리가 된다. 또는 서버 상태에 따라 시간초과가 뜨는 경우가 있다. 아래는 관련 코드다.

import sys
m = int(sys.stdin.readline()) # 조금이라도 시간을 줄이기 위해 sys 임포트
l = [0]*m
count = 0
def check(a): # 가지치기
    if a==0: return True # 사실 삭제해도 되지만 남겨놓는 쪽이 속도가 조금 더 빠르다
    for i in range(a): # 0부터 a-1까지만 for문을 돌린다는 것에 주의
        if l[a]==l[i] or abs(l[a]-l[i])==a-i: return False # a는 항상 i보다 큼. 이전에 놓은 말들이 공격할 수 있는 위치에 있는지 확인
    return True
def fun(depth):
    global count
    if depth == m:
        count += 1
        return
    for i in range(m): 
        l[depth]=i
        if check(depth): # 안전이 확보되면 현재 자리에 퀸을 놓고 다음 단계로 진행
            fun(depth+1)
fun(0)
print(count)