BAEKJOON-9663 : N-Queen

BEAKJOON-1018 : N-Queen

시간초과 때문에 쩔쩔 맸던 문제이다. 어떻게든 실행시간을 줄이려고 노력했다.

python3로는 시간초과가 뜨고 pypy3? 으로는 겨우 통과가 된다.

편법말고 실행시간을 더 줄일 수 있는 효율적인 코드를 생각해봐야겠다..

코드

from sys import stdin
n = int(stdin.readline())
total = 0
arr = [[False for _ in range(n)] for _ in range(n)]

def conflict(row, col):
    global arr
    for i in range(row):
        if col-i > 0:
            if arr[row-i-1][col-i-1]:
                return True
        if col+i < len(arr)-1:
            if arr[row-i-1][col+i+1]:
                return True
        if arr[row-i-1][col]:
            return True

    for i in range(len(arr)-row-1):
        if col-i > 0:
            if arr[row+i+1][col-i-1]:
                return True
        if col+i < len(arr)-1:
            if arr[row+i+1][col+i+1]:
                return True
        if arr[row+i+1][col]:
            return True
    return False

def search(row, col):
    global arr
    global total
    if conflict(row, col):
        return 0
    if row == len(arr)-1:
        return total + 1
    for i in range(len(arr)):
        arr[row+1][i] = True
        total = max(total,search(row+1, i))
        arr[row+1][i] = False
    return total

for i in range(n//2):
    arr[0][i] = True
    total = max(total, search(0, i))
    arr[0][i] = False
total *= 2
if n%2:
    arr[0][n//2] = True
    total = max(total, search(0, n//2))
print(total)

퀸의 이동 방향을 생각해보면

가로,세로, 우상향 대각선, 우하향 대각선 방향으로 이동할 수 있다.

그래서 conflict(충돌 감지 함수)에서 가로를 제외한 나머지 방향에서 충돌이 나는 지 확인한다.

가로 방향을 제외한 이유는 말을 둘 때 같은 이전 행에서 말을 두었으면 다음 행으로 넘어가기 때문이다.

즉, 같은 행에 말이 없기 때문에 행을 비교할 필요가 없다.