[Python]백준 9663 - N-Queen

백준 9663-N-Queen

문제

코드

import sys

input = sys.stdin.readline


def backtracking(qNum):
    if qNum == N:
        global cnt
        cnt += 1

    for i in range(N):
        if not visited[i]:
            if check(qNum, i):
                visited[i]=True
                l[qNum] = i
                backtracking(qNum + 1)
                visited[i]=False



def check(x, y):
    for i in range(x):
        if (x - i == abs(l[i] - y)):
            return False
    return True


N = int(input())

l = [0] * N
visited = [False] * (N)
cnt = 0
backtracking(0)
print(cnt)

해설

먼저 해당 문제는 Phyton3로 돌리면 시간초과가 계속 나 pypy3로 돌렸다.

풀이방법
1. 백트래킹 이용
2. x값은 배열의 순서(?)와 같으므로 1차원인 리스트 사용
3. check로 대각선인 경우를 체크해줌
=> (x - i == abs(l[i] - y)
4. visited로 동일 세로 줄일 경우 중복적으로 체크 하는것 방지