난이도

Gold 4

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력

예제 출력

해설

유명한 N-Queen문제이다. 처음에는 무턱대고 이차원 배열로 체스판을 만들어 퀸을 놓을때마다 판을 바꾸고 이에 따라 백트래킹하는 방식을 생각했었는데, 이내 이 방식이 상당히 비효율적임을 깨닫게 되었다. 많은 해설에서 다루듯, 일차원 배열만을 사용해 N-Queen문제의 배치를 구현할 수 있었고 이를 이용해 백트래킹한다.

제출 코드

import time
start_time = time.time()

n = int(input())
cnt = 0

def dfs(lst, visit):
    global cnt
    now = len(lst) #새로 추가할 행 번호
    if(now == n):
        cnt += 1
        return
    
    banned = visit[:]#다음으로 선택할 수 없는 것
    for i in range(now):
        a = now-i+lst[i]
        b = i+lst[i]-now
        for j in [a,b]:
            if(j>=0 and j<n):
                banned[j] = 1

    for i in range(n):
        if(banned[i] == 0):
            nextVis = visit[:]
            nextVis[i] = 1
            dfs(lst+[i], nextVis)
    return

dfs([],[0 for i in range(n)])
print(cnt)

end_time = time.time()
execution_time = end_time - start_time

#print(f"Execution time: {execution_time} seconds")