9663:N-Queen [백준 문제풀이][Python][CLASS 4]

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

 

n*n 격자판 위에 n개의 퀸을 배치할때, 퀸이 서로를 공격하지 못하게 배치하는 경우의 수를 구하시오.

이런 식으로 퀸을 배치하면 된다.

백트래킹을 이용하는 굉장히 유명한 문제이다.

아이디어

백트래킹을 이용해서 위쪽 줄부터 차례대로 재귀함수를 사용해 탐색하면서 내려가면 된다.

이때 겹치는 세로줄,대각선을 체크하여 들어갈 수 있는지 확인하기 위한 리스트를 만든다.

퀸의 경로를 체크하는 3가지 배열

 

우하향,우상향 대각선을 분리해서 생각해주었다. 퀸이 있는 자리에 배열 값을 바꿔주면서 내려와서 마지막줄에 도달하면, count +=1을 해주어 개수를 세었다.

각 x,y에서 col1,diag1,diag2의 어떤 값이 올지 생각해주는게 관건이었던거 같다.

정답 코드

n=int(input())
col1=[0]*n#세로
diag1=[0]*(2*n +1)#우하향
diag2=[0]*(2*n +1)#우상향
count=0
def search(y):
    global count
    if(y== n):
        count += 1#마지막줄까지 도착했다면
        return
    for x in range(0,n):
        if(col1[x] or diag1[x+y] or diag2[n+x-y-1]):continue
        else:
            col1[x] = diag1[x+y]  = diag2[n+x-y-1] = 1#퀸의 경로 체크
        search(y+1)#다음 줄로
        col1[x] = diag1[x+y]  = diag2[n+x-y-1] = 0#탐색이 끝났으면 퀸 회수
search(0)
print(count)