[Python/SWEA] 2806. N-Queen

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB 

SW Expert Academy

문제

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다.

퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.

N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?

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

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 N(1 ≤ N ≤ 10)이 주어진다.

 

출력

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

풀이

Code

# 1. 현재 위치에 퀸 배치 가능 여부 함수 선언
def check(x):
    # 1-1.
    for i in range(x):
        # 같은 열에 있거나 대각선 위치에 있는 경우 False 반환
        if queen[i] == queen[x] or abs(queen[x] - queen[i]) == x - i: return False
    # 1-3. 배치 가능 시 True 반환
    return True
# 2. dfs 함수 선언
def dfs(x):
    global ans
    # 2-1. 종료 조건 설정
    if x == n: ans += 1
    # 2-2.
    for i in range(n):
        # 열 설정
        queen[x] = i
        # 현재 위치에 퀸 배치 가능 시 dfs 실행
        if check(x):
            dfs(x + 1)

T = int(input())
for test_case in range(1, T + 1):
    n = int(input())
    queen = [0] * (n+1)
    ans = 0
    dfs(0)
    # 3. 결과 출력
    print(f'#{test_case} {ans}')

Code Review