[추석맞이 코딩챌린지 Bonus] 공격할 수 없는 Queen

https://cafe.naver.com/codeuniv/45014

[추석맞이 코딩챌린지 Bonus] 공격할 수 없는 Queen

 

예를 들어 n = 5 이고 col = [0, 2, 4, 1, 3] 이면, (0, 0), (1, 2), (2, 4), (3, 1), (4, 3) 의 위치에 퀸을 배치한 상태이다. 퀸이 문제의 조건에 만족하도록 배치할 수 있는 col 의 개수를 반환하면 된다.

 

퀸을 놓을 수 있는 경우를

 

1. for j in range(row): if i != col[j] : 같은 열에 하나의 퀸만 배치할 수 있다. (세로로 공격할 수 없음, 가로는 행으로 구분이 되어 있음)

 

2. for j in range(row): if abs(i - col[j]) != row - j : 같은 대각선에 하나의 퀸만 배치할 수 있다.

 

를 만족하면서 row 가 N 에 도달할 수 있는 경우가 N 개의 퀸이 서로 공격할 수 없는 경우이다.

 

import sys

N = int(sys.stdin.readline())
answer = 0
col = [0] * N

def nqueen(N, row, col):
    global answer
    
    if row == N:
        answer += 1

    for i in range(N):
        t = True
        
        for j in range(row):
            if i == col[j] or abs(i - col[j]) == row - j:
                t = False
                break   
        if t:
            col[row] = i
            nqueen(N, row+1, col)
    
nqueen(N, 0, col)

print(answer)