[백준 9663번 Python] N-Queen

백트래킹을 제대로 배울 수 있는 기본 문제.(사실 기본 문제라고 하기엔 처음엔 너무 어려웠다....)

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

9663번: N-Queen

N-Queen 문제 풀이시 Check Point

1. 상하, 좌우, 대각선에서 좌우의 경우 DFS에서 Level 단위(column)로 내려가기 때문에 고려할 필요가 없다. [check 함수 1번째 조건문]
2. 대각선의 경우 for loop를 돌며 0에서 현재 있는 좌표까지 x 좌표의 차의 절대값과 y 좌표의 차의 절대값이 동일하다면 False를 반환하여 DFS를 실행할 때 현재 지목된 좌표에서 다음 단계로 넘어갈지 아닐지를 결정한다. [check 함수 2번째 조건문]
3.  만약 Check 함수에서 다음 단계로 넘어가지 못한다면 기존에 지정했던 인덱스를 0으로 초기화한다.
4. 모든 배열을 탐색한 경우(level==N) 퀸을 놓을 수 있는 한 가지 경우의 수를 확인한 것이므로 cnt++
5. N-Queen 문제에서의 배열은 1차원 배열(arr)이며, 해당 배열의 인덱스는 x 좌표를, 인덱스안의 값은 y좌표를 의미한다.

 

import sys

N =int(sys.stdin.readline())
arr=[0 for _ in range(N)]

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

cnt =0

def DFS(level):
    global cnt
    if level==N:
        cnt+=1
        return
    
    for i in range(N):
        arr[level]=i
        if check(level):
            DFS(level+1)
        arr[level]=0

DFS(0)
print(cnt)

 

다하고나니 pypy3으로 제출해야 시간초과가 나지 않는다. 왜일까..다음에 공부해서 올려야지.