1. 문제
  2. 접근
  3. 풀이

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

접근

N-Queen 문제는 백트래킹을 이용하는 유명한 문제중 하나이다.
백트래킹이란, 해를 찾는 과정에서 유망성을 판단하고(promising) 유망하지 않은 후보 해에 막히면 되돌아가서(back track) 다른 해를 찾아가는 기법을 말한다. 백트래킹을 트리 탐색 기법의 한 종류로 분류할 수는 없다. 그러나 백트래킹을 DFS와 접목하면, 모든 노드를 방문하고 검색하지 않아도 되어 이득을 볼 수 있어 많이 사용된다.

N-Queen 문제의 경우, 총 N개의 퀸을 하나씩 배치해보면서 유망성 검사(promising)을 통해 더이상 퀸을 배치할 수 없는 상황에 도달하면, 전 단계로 되돌아가 다른 경우를 시도해본다. 퀸은 같은 열, 같은 행, 같은 대각선에 다른 퀸이 위치하는지 판단함으로써 유망성 검사를 할 수 있다.
처음에는 퀸의 위치좌표를 저장해가면서 x,y,대각선을 비교하는 방법으로 접근했으나, 훨씬 간단한 방법을 발견할 수 있었다. 각 행의 몇 번째 열에 퀸이 놓여있는지를 행렬로 저장하면, 행은 겹칠일이 없고, 열과 대각선만 비교하면 된다.

promising function
1
2
3
4
5
def promising(idx):
  for i in range(idx):
    if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
      return 0
  return 1

기본적인 DFS의 틀을 따라가면서, 행렬의 길이가 N이 되었을 때(N개의 퀸을 성공적으로 배치했을 때)만 count해주면 된다.

풀이

BOJ 9663 N-Queen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
N = int(input())
queen = [0]*(N)
count = 0

def promising(idx):
  for i in range(idx):
    if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == idx - i:
      return 0
  return 1

def dfs(idx):
  global count
  if idx == N:
    count += 1
    return
  for i in range(N):
    queen[idx] = i
    if promising(idx):
      dfs(idx+1)

dfs(0)
print(count)