[🥇4 / 백준 9663 / 파이썬] N-Queen

 

9663번: N-Queen

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

예제 입력  8

예제 출력  92

 

풀이

 

 

백트래킹으로 유명한 예제 중 하나라고 한다.

 

파이썬으로도 풀 순 있지만, 무거운 언어이다 보니 시간 초과가 발생한다.

동일한 코드를 PyPy3로 제출하면 정답으로 처리된다.

 

 

퀸은 기본적으로 수직, 수평, 대각선으로 공격이 가능하다.

 

우선 수직, 수평만 생각해봤을 때, 

N x N 의 체스판에 N 개의 퀸을 두려면 무조건 가로, 세로 줄 마다 하나씩은 놓여야 한다.

 

따라서 첫 번째 가로줄부터 시작해서 차례대로 퀸을 놓아주고,

퀸을 놓았다면 다음 줄로 가서 퀸을 놓는 로직을 사용할 것이다.

 

여기서, 재귀가 필요함을 알 수 있다.

 

위와 같이 차례로 내려가며 퀸을 둔다.

 

8 x 8 체스판을 예를 들자.

row = [[0]*8 for i in range(8)]

 

이렇게 8 x 8 의 2차원 배열을 만들어 풀 것이다.

 

알고리즘의 순서는 이렇다.

 

1. 현재 줄의 퀸이 놓일 자리에 수직상에 다른 퀸이 있는지 판별한다.
2. 없다면 대각선으로도 판별한다.
3. 대각선에도 없다면 퀸을 놓고 다음 줄로 넘어간다.
4. 마지막 줄이라면 모든 퀸이 놓였으므로 카운트하고 다시 퀸을 뺀 뒤, 이전 줄로 돌아가 순환한다.

 

아래는 정답 코드이다.

 

n = int(input())

row = [[0]*n for i in range(n)]
count = 0

def queen(a):
    
    if a == n:
        global count
        count+=1
        return
    # 퀸이 모두 놓였으므로 카운트하고 종료
    
    for i in range(n):
        skip = 0
        for j in range(n):
            if row[j][i] == 1:
                break
       	# 수직상의 퀸 검사
        else:
            for k in range(a):
                if (row[k].index(1) == i + a-k) | (row[k].index(1) == i - (a-k)):
                # 대각선상의 퀸 검사
                    skip = 1
                    break
            if skip == 1:
                continue
                # 반복문 두 개를 한번에 건너뛸 수 없으므로
                # 변수를 활용해준다.
            row[a][i] = 1
            queen(a+1)
            row[a][i] = 0
        
queen(0)
print(count)