Python으로 푸는 SW Expert Academy 2806. N-Queen

SW Expert Academy 2806. N-Queen

체스판에서 퀸은 같은 가로, 세로줄, 대각선에 위치한 체스말을 잡을 수 있다.

이러한 특징을 이해하고 각 가로줄마다 퀸을 놓을 수 있는 경우의 수를 

알아낼 수 있는 코드를 짜보자

삼성 SW Expert Academy에서 푼 문제 보기

github에서 코드 보기

문제 풀이

퀸을 한줄마다 놓을 때, 가로, 세로, 대각선에 위치한 퀸인지 확인한다. 

맨 마지막이 될때까지 모든 퀸을 놓을 수 있으면 count를 증가시킨다.

모든 경우의 수를 탐색하지만, 퀸을 놓을 수 있는 자리인지를 확인하고 놓을 수 없을 경우에 backtracking하는 방법으로 코드를 짰다.

문제에서 다른 예시가 필요할 수도 있어서 아래 남겨두도록 하겠다.

n = 1, output : 1

n = 2, output : 0

n = 3, output : 0

n = 4, output : 2

n = 5, output : 10

n = 6, output : 4

n = 7, output : 40

n = 8, output : 92

n = 9, output : 352

n = 10, output : 724

파이썬 코드

from copy import deepcopy
 
 
def Checkdiagnal(pos, queenlist):
    x, y = pos
    for queen in queenlist:
        qx, qy = queen
        if abs(x - qx) == abs(y - qy):
            return False
    return True
 
 
def otherQueen(b, queenlist, col, cur, end):
    global count
    for i in range(n):
        # 놓아도 되는 자리
        if col[i]:
            # diagnal 체크
            if Checkdiagnal((cur, i), queenlist):
                if cur == end:
                    count += 1
                    break
                b[cur][i] = 1
                col[i] = False
                queenlist.append((cur, i))
                otherQueen(b, queenlist, col, cur + 1, end)
                b[cur][i] = 0
                col[i] = True
                queenlist.pop()
 
 
def solve(n):
    global count
    if n <= 1:
        return n
    col = [True]*n
    board = [[0]*n for i in range(n)]
    queenlist = []
    otherQueen(board, queenlist, col, 0, n-1)
    return count
 
 
if __name__ == "__main__":
    t = int(input().strip())
    for n in range(1, t+1):
        i = int(input().strip())
        count = 0
        print("#{0} {1}".format(n, solve(i)))

#sw expert 2806 N-Queen #sw expert 2806 python #sw expert 2806 파이썬 #2806 N-Queen