#196 백준 파이썬 [9663] N-Queen

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

 

#Solution

정답 코드(시간 초과)

https://www.acmicpc.net/board/view/25761이 문제에 대해 파이썬 문의글. 시간 초과 때문에 되도록 파이썬을 이용하지 않도록 권장하고 있다. 또한 백트래킹 대부분의 문제는 파이썬으로 풀기 부적합하다(시간 복잡도 상).

실제로 파이썬으로는 정석적으로 풀기 힘들다. 매우 많은 조건문을 통해 유망한 자식들을 걸러줘야한다.

기본적인 알고리즘은 다음과 같다.

 

1) N개의 퀸을 배치해야하므로 무조건 모든 행에 퀸이 들어가야한다.

2) 따라서 0열부터 N-1열까지 퀸을 놓는 방법을 for문을 통해 돌린다.

3) 유망한지(이전의 열로 인해 영향을 받는지) 검사하는 함수 adjacent를 통해 유망함수만을 걸러준다.

 

사실 adjacent 갈때마다 chess map(현재까지의 배치도, 이전 까지 모든 퀸의 경로와 겹치는 곳을 1로, 안겹치는 곳은 0으로 표시)를 이용하면 훑을 수 있을 것 같다. 하지만 귀찮으므로 패스

 

#내 윗줄에 나와 겹치는 라인에 퀸이 있는가?
def adjacent(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True
        
        
#한줄씩 재귀하며 DFS를 실행
def dfs(x):
    global result
    
    if x == N:
        result += 1

    else:
        for i in range(N):
            row[x] = i
            if adjacent(x):
                dfs(x + 1)

N = int(input())
row = [0] * N
result = 0
dfs(0)
print(result)

 

정답 코드(야매)

그렇다. 인풋 15개 정도는 답을 구해서 쓸 수 있다. 인간은 언제나 답을 찾을 것이다.

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])