백준 9663 [N-Queen] 파이썬

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

9663번: N-Queen

# 백준 9663 N-Queen
import sys
N = int(input())
field = [[0]*(N) for _ in range(N)]
answer = 0


def search(n, N, curr):
    global answer
    if n == N:
        answer += 1
    else:
        for i in range(N):
            if curr[n][i] == 0:
                new = []
                for k in range(N):
                    new.append(list(map(int, curr[k])))
                for r in range(N):
                    for c in range(N):
                        if r == n:
                            new[r][c] = 1
                        elif c == i:
                            new[r][c] = 1
                        elif r-c == n-i:
                            new[r][c] = 1
                        elif r+c == n+i:
                            new[r][c] = 1
                search(n+1, N, new)


search(0, N, field)
print(answer)

각 퀸이 놓일때마다 배열을 갱신해 나가면서 새로운 배열을 재귀적으로 전달하는 방식으로 해결하려고 하였다. 하지만, 배열을 새로 만들어서 그런지.... 시간초과가 발생하였다...

# 백준 9663 N-Queen
def check(n):
    for k in range(n):
        if queen_row[n] == queen_row[k] or abs(queen_row[n]-queen_row[k]) == n-k:
            return False
    return True


def search(n):
    global answer
    if n == N:
        answer += 1
    else:
        for i in range(N):
            queen_row[n] = i
            if check(n):
                search(n+1)


N = int(input())
answer = 0
queen_row = [0]*(N)
search(0)
print(answer)

다른 분의 풀이를 참고하여 문제를 해결하였다. 핵심은 queen_row를 사용하여, 각 index(행)별로 배열값을 저장하고, 이 배열을 계속 이용하는 방식이었다..

 

더 연습해야겠다...