[SWEA 2806번] N-Queen - 파이썬(python)

SW Expert Academy

문제

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

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

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

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

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

입력

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

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

출력

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

풀이

• 퀸을 놓는 자리가 같은 행이나 같은 열에 위치하면 안되고 대각선으로도 같은 선상에 있으면 안된다.
• 따라서 방문 여부를 확인하면서 같은 행, 같은 열을 피하도록 함수를 만들었다.
• 대각선도 확인을 해야 하므로 퀸을 하나 놓을 때마다 대각선에 다른 퀸이 있는지 확인한다.
• 대각선에 퀸이 있는지 확인하는 방법을 모르겠어서 찾아봤다.
• 결론은 x좌표끼리 뺀값의 절댓값과 y좌표끼리 뺀값의 절댓값이 같다면 대각선상에 있다는 것을 알아야 한다.

코드

def check(tm):
    # 대각선 검사 방법
    # x좌표끼리 뺀값의 절댓값 = y좌표끼리 뺀값의 절댓값 대각선 관계
    for i in range(tm):
        if abs(tm-i)==abs(chess[tm]-chess[i]):
            return 0
    return 1


def queen(num):
    global cnt
    # 퀸을 전부 놓으면 카운트
    if num == N:
        cnt+=1
        return
    # 첫번째 줄부터 하나씩 채우기
    for i in range(N):
        # 방문했다면 continue
        if visit[i]==1:continue
        # 체스의 num번째 줄의 i칸에 퀸을 놓기
        chess[num]=i
        # 놓은 퀸이 대각선 검사를 통과하는지 확인하기
        if check(num):
            # 통과한다면 방문 체크하고 다음줄 퀸 놓기
            visit[i] = 1
            queen(num+1)
            visit[i] = 0


T = int(input())
for test_case in range(1, T + 1):
    N= int(input())
    # 퀸을 놓는 자리를 (인덱스, 값)의 형태로 저장
    chess=[-1]*N
    visit = [0]*N
    cnt=0
    queen(0)
    print(f'#{test_case} {cnt}')