[Python] 백준 9663_ N-Queen

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

**다음 내용은 유튜브 '바킹독'님의 백트래킹 강의를 듣고 작성한 내용이다. (youtube.com/watch?v=Enz2csssTCs&t=1237s)

이 문제는 백트래킹을 이용하여 해결할 수 있는 문제이다.

체스에서 퀸은 일직선으로 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동가능하므로 먼저 열(앞/뒤), 상향 대각선, 하향 대각선 방향에 이미 말이 존재하는지 체크를 해준다.

check1 =[True]*n #열확인 
check2 =[True]*(n*2-1) #대각선확인 (x+y)
check3 =[True]*(n*2-1) #대각선확인 (y-x)

1. check1 : 열확인
   

2. check2: 상향 대각선 확인
   예를 들어, 인덱스 (2,2), (1,1), (0,2)는 한 대각선에 위치한다.
   이때 (x,y)에서 x+y는 모두 같은 것을 확인할 수 있다.

3. check: 하향 대각선 확인
   예를 들어, 인덱스 (0,1),(1,2),(2,3)는 한 대각선에 위치한다.
   이때 (x,y)에서 y-x는 모두 같은 것을 확인할 수 있다.

코드

import sys
input = sys.stdin.readline

n = int(input())
#퀸은 일직선으로 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동가능

check1 =[True]*n #열확인 
check2 =[True]*(n*2-1) #대각선확인 (x+y)
check3 =[True]*(n*2-1) #대각선확인 (x-y)
cnt=0

def func(num):
    global cnt
    
    if num ==n: #퀸을 모두 체스판에 놓았으면 cnt+=1
        cnt+=1
        return

    for i in range(n):
        if check1[i] and check2[i+num] and check3[num-i+n-1]: 
        #모두 조건을 만족하면(check3: num-i+n-1인 이유는 계산한 값이 음수가 되는 것을 방지하기 위해서이다.)
            check1[i]=False
            check2[i+num]=False
            check3[num-i+n-1]=False
            func(num+1)
            check1[i]=True
            check2[i+num]=True
            check3[num-i+n-1]=True
func(0)
print(cnt)