[Baekjoon] 9663번 : N-Queen

1. 문제

https://www.acmicpc.net/problem/9663

• 백트래킹 문제

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

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

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

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

// 예제 입력 1
8

// 예제 출력 1
92

2. 핵심 아이디어

• N x N 크기의 체스 보드 위에 퀸 N개를 서로 공격할 수 없게 배치
• 대표적인 백트래킹 문제
• DFS를 이용하여 간단히 백트래킹 알고리즘을 구현할 수 있음
• 각 행을 차례대로 확인하면서, 각 열에 퀸을 놓는 경우를 고려
• PyPy3 제출

3. Python 문제풀이

import sys
input = sys.stdin.readline

# x번째 행에 놓은 Queen에 대해서 검증
def check(x) :
  # 이전 행에서 놓았던 모든 Queen들을 확인
  for i in range(x) :
    # 위쪽 혹은 대각선을 확인
    if row[x] == row[i] :
      return False
    if abs(row[x] - row[i]) == x - i :
      return False
  return True

# x번째 행에 대하여 처리
def dfs(x) :
  global result
  if x == n :
    result += 1
  else :
    # x번째 행의 각 열에 Queen을 둔다고 가정
    for i in range(n) :
      row[x] = i
      # 해당 위치에 QUeen을 두어도 괜찮은 경우
      if check(x) :
        # 다음 행으로 넘어가기
        dfs(x + 1)

n = int(input())
row = [0] * n
result = 0
dfs(0)
print(result)

4. Java 문제풀이

import java.util.Scanner;

public class Main {
  public static int n;
  public static int count;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    for (int i=1; i<=n; i++) {
      int[] col = new int[n+1];
      col[1] = i;
      dfs(col, 1);
    }
    System.out.println(count);
  }

  public static void dfs(int[] col, int row) {
    if (row == n) {
        count++;
    } else {
      for (int i=1; i<=n; i++) {
        col[row+1] = i;
        if (check(col, row+1)) {
          dfs(col, row+1);
        }
      }
    }
  }

  public static boolean check(int[] col, int row) {
    for (int i=1; i<row; i++) {
      if (col[i] == col[row]) return false;
      if (Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;
    }
    return true;
  }
}