[백준(Baekjoon)] 9663 N-Queen

문제

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

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

 

입력

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

 

출력

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

 

입력	출력
8	92

 

---

나의 풀이

[파이썬(Python)]

 

풀이 1 - 시간초과 

import sys
input = sys.stdin.readline
n = int(input())
board = [0] * n  # 열
case = 0

def chess(cnt):
    global case
    if cnt == n:    # n개 퀸 배치했다면 종료
        case += 1
        return
    for i in range(n):
        board[cnt] = i
        if cnt == 0 or check(cnt):
            chess(cnt+1)


def check(cnt):
    for j in range(cnt):
        if board[cnt] == board[j] or cnt-j == abs(board[cnt]-board[j]):
            return False
    return True

chess(0)
print(case)

 

---

 

풀이 과정

이 문제는 파이썬은 통과할 수 없는 문제인 듯 했다. 다들 시간초과가 나온다고,,, 그럼 통과한 사람들은 어떻게 통과했나 찾아보니 문제에 몇가지 경우가 없으니까 그냥 답을 구한 다음에 리스트에 넣어서 바로 출력하는 것이었다. 

 

chess = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(chess[int(input())])

 

파이썬은 백트래킹 구현하기에 아주 부적합하다는 것ㅠㅠ

 

 

---

그래도 코드는 구현했으니 풀이 과정을 알아보도록 하자

체스해 본 적이 없는 나는 퀸이 어떠한 규칙을 가지고 있는지 체스 규칙부터 알아야했다....^^ 

 

퀸(Queen)
체스의 기물들 중 하나로, 가장 가치 있는 기물
퀸은 자신의 주위 모든 방향으로 움직일 수 있다.( 상하좌우, 대각선 모두 공격 할 수 있다. )

 

 

---

• 백트레킹으로 N-Queen 구현

 

 

 

계속 진행하다가 막히는 곳이 있으면 다시 그 전 행으로 돌아가서 재배치한 후 진행한다. 

 

 

board: 열 또는 행 기준
case : 퀸을 놓는 방법의 수 
cnt = 배치한 퀸의 개수

 

1. 가로, 세로 체크

 

행을 기준으로 생각해보자

퀸을 board[1, 3, 0, 2]에 배치했다고 하면

0행 1열

1행 3열

2행 0열

3행 2열에 배치한 것이다. 

 

인덱스 0 - 3에 각 각 숫자 한 개씩 있으니 행에는 한개의 퀸을 배치함을 알 수 있어서 더 이상 검사할 필요가 없고 

열은 board 리스트에 같은 숫자가 없으면 된다. 

 

ex) [1, 2, 1, 3]이라면 1열에 2개의 퀸이 있다는 뜻 -> 배치 불가

# 같은 열에 배치된 퀸이 있는지 검사
if board[cnt] == board[j]

 

2. 대각선 체크

 

cnt-j == abs(board[cnt]-board[j])

위의 코드를 통해 대각선 검사를 한다. 

 

 

3. 퀸을 놓은 방법 수 계산

    if cnt == n:    # n개 퀸 배치했다면 종료
        case += 1
        return

cnt : 현재까지 배치한 퀸의 개수

n : 배치해야할 퀸의 개수

 

현재까지 배치한 퀸의 개수가 배치해야 할 퀸의 개수와 같다면 case를 1 증가 시킨다. 

 

 

 

---

다른 사람 코드 - python 시간초과, pypy 통과 

import sys
input = sys.stdin.readline
n = int(input())
case = 0

col_check = [0] * n
d1_check = [0] * n*2
d2_check = [0] * n*2

def chess(cnt):
    global case
    if cnt == n:    # n개 퀸 배치했다면 종료
        case += 1
        return
    for i in range(n):
        if col_check[i] == 0 and d1_check[cnt+i] == 0 and d2_check[cnt-i+n-1] == 0:
            col_check[i] = d1_check[cnt+i] = d2_check[cnt-i+n-1] = 1
            chess(cnt+1)
            col_check[i] = d1_check[cnt+i] = d2_check[cnt-i+n-1] = 0

chess(0)
print(case)

대각선 체크 배열을 따로 두어 이전에 배치한 것을 포문으로 돌아볼 필요없기 때문에 시간이 줄어든다. 

 

---

문제 출처

9663번: N-Queen

 

퀸

퀸(Queen) - 체스 용어