[백준] 9663번 - N-Queen

백트래킹 문제라는 것만 기억나고 방법을 정말 모르겠어서...유튜브 영상(https://www.youtube.com/watch?v=z4wKvYdd6wM&t=925s)을 보면서 학습했다

개념 및 설명

퀸을 서로 잡아먹히지 않게 하려면 같은 행, 열, 대각선에 퀸을 두면 안된다.
1) 같은 행에 퀸을 놓지 않는다.
2) 같은 열이나 같은 대각선에 퀸이 있는지 확인

1차 시도

# N-Queen
def promising(i,col):
    k = 1
    check = True
    while(k < i and check):
        # 같은 열에 있거나 대각선에 있는지 검사
        if (col[i] == col[k] or abs(col[i] - col[k]) == (i-k)):
            check = False
        k += 1
    return check

def n_queens(i,col):
    global result
    n = len(col) - 1 # depth
    if promising(i,col):
        if i == n:
            result += 1
        else:
            for j in range(1,n+1):
                col[i+1] = j
                n_queens(i+1,col)

N = int(input())
col = [0] * (N+1)
result = 0
n_queens(0,col)
print(result)

시간초과

최종

# N-Queen
import sys
def promising(i,col):
    k = 1
    while k < i:
        # 같은 열에 있거나 대각선에 있는지 검사
        if (col[i] == col[k] or abs(col[i] - col[k]) == (i-k)):
            return False
        k += 1
    return True

def n_queens(i,col):
    global result
    n = len(col) - 1 # depth
    if promising(i,col):
        if i == n:
            result += 1
        else:
            for j in range(1,n+1):
                col[i+1] = j
                n_queens(i+1,col)

N = int(sys.stdin.readline().strip())
col = [0] * (N+1)
result = 0
n_queens(0,col)
print(result)

pypy로 바꾸고 sys함수 사용