[Baekjoon] 9663. N-Queen

N-Queen

문제 설명

---

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

문제 풀이

---

N-Queen은 유명한 백트래킹 문제이다.

1번 풀이(14396ms, PyPy3)

col_loc이라는 queen들의 열의 위치를 저장하는 리스트를 만들고, 해당 위치에 놓을 수 있는 지 검사하기 위해 col_loc의 값들을 이용해 계산을 합니다.

col_loc = [] # 0~7번째 행에 위치한 열의 위치
def find_nqueen(N, row, cnt):
    global col_loc
    if row == N:
        return cnt+1

    for col in range(N):
        for line in range(len(col_loc)):
            # 1. 같은 열인지, 2. 같은 우상향 대각선인지, 3. 같은 우하향 대각선인지
            if col == col_loc[line] or row + col == line + col_loc[line]\
                                    or row - col == line - col_loc[line]:
                break
        else:
            col_loc.append(col)
            cnt = find_nqueen(N,row+1,cnt)
            col_loc.pop()

    return cnt

print(find_nqueen(int(input()),0,0))

2번 풀이(6860ms, PyPy3)

열의 위치를 저장하는 것이 아니라, queen이 배치될 때마다 해당 위치의 열, 우상향 대각선, 우하향 대각선을 True로 설정하여 다른 queen이 배치되지 못하도록 합니다.

해당 풀이의 경우 정석적인 풀이라고 볼 수는 없지만, 계산 과정이 없고 인덱스 참조만 하기 때문에 시간이 훨씬 줄어듭니다.

n = int(input())
count = 0
column,rightup,rightdown = [False]*n,[False]*(2*n-1),[False]*(2*n-1)

def NQueen(line):
  global count
  if line == n:
    count += 1
    return
  else:
    for index in range(n):
      if not (column[index] or rightup[line+index] or rightdown[line-index+n-1]):
        column[index] = rightup[line+index] = rightdown[line-index+n-1] = True
        NQueen(line+1)
        column[index] = rightup[line+index] = rightdown[line-index+n-1] = False

NQueen(0)
print(count)

파이썬은 가독성이 좋은 interpreter 언어이기 때문에 compiler 언어들보다 속도면에서 확연하게 느립니다.

따라서 이러한 재귀 알고리즘에 있어 파이썬 언어는 좋은 선택은 아닙니다. 실제로 PyPy3가 아닌 Python3로 제출 시 시간 초과가 발생합니다.