1. 문제 설명

N-Queen

2. 문제 분석

DFS를 통해 지금까지 놓은 퀸과 다른 행을, for 문 내에서 열과 대각선이 다른 퀸 위치를 체스 판에 넣는다. 행을 하나씩 추가하면서 행이 n이라면 (즉 0행부터 n-1행까지 모두 탐색 성공했다면) 퀸을 놓을 수 있다는 뜻이다.

• DFS를 재귀 형식으로 구현했고, 이차원 배열이 아니라 queens라는 n개 리스트를 통해 (row, col)을 표현했다.

3. 나의 풀이

n = int(input())

def DFS(queens, row, n):
    if row == n: return 1
    # n-1까지 모두 퀸을 놓았다. n-queens 성공

    total = 0
    for col in range(n):
        queens[row] = col
        # (row, col)에 퀸을 놓는다.
        queenable = True

        for i in range(row):
            # 지금까지 놓은 퀸 (앞의 행들)과 부합하지 않는 퀸이 있는지 확인하자.
            if queens[i] == queens[row] or abs(queens[i]-queens[row]) == abs(row - i):
                queenable = False
                break
        if queenable:
            total += DFS(queens, row+1, n)
    return total

queens = [0]*n
total = DFS(queens, 0, n)
print(total)

• 백준에서는 파이썬으로 시간 초과가 난 코드인데, pypy로 제출했을 때에는 성공했다. 어떻게 파이썬으로 시간 단축할 수 있을까?