[BOJ] 9663번 N-Queen

문제

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

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

입력

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

출력

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

코드

• C++ 17

#include <iostream> #include <cmath>   using namespace std;   // cols[row] => 퀸이 (row, cols[row])에 위치해 있다. int cols[15]; int N, Ans;   // N-Queen 문제는 전형적인 백트래킹 문제이다. // 다음 함수는 유망성을 검사하는 함수이다. bool canPlace(int bound) {     // 이전까지 배치된 퀸의 위치를 순회하며 배치 가능한지 검사한다.     for (int r = 0; r < bound; ++r)     {         // 같은 열인가         if (cols[bound] == cols[r])             return false;         // 같은 대각선인가         else if (abs(cols[bound] - cols[r]) == abs(bound - r))             return false;     }       return true; }   // DFS 함수이다. // 구현에 따라서는 int 값을 반환하게 할 수 있다. void queen(int r) {     // 모든 행에 배치가 다 되었다면 경우의 수를 1 증가한다.     if (r == N)         ++Ans;     else     {         // 모든 열을 돌면서 배치해본다.         for (int c = 0; c < N; ++c)         {             // 퀸을 배치한다.             cols[r] = c;               // 유망성을 검사한다.             if (canPlace(r))             {                 // 다음 행으로 넘어간다.                 queen(r + 1);             }         }     }       // 배치를 취소한다.     cols[r] = 0; }   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       cin >> N;       queen(0);       cout << Ans; }

• C# 6.0

using System;   namespace ForAlgoCsharp {     class Program     {         static int N;         static int[] Cols = new int[15];           static bool CanPlace(int bound)         {             for (int r = 0; r < bound; ++r)             {                 if (Cols[bound] == Cols[r])                     return false;                 else if (Math.Abs(Cols[bound] - Cols[r]) == Math.Abs(bound - r))                     return false;             }               return true;         }           static int Queen(int r)         {             int toRet = 0;               if (r == N)                 return 1;             else             {                 for (int c = 0; c < N; ++c)                 {                     Cols[r] = c;                     if (CanPlace(r))                     {                         toRet += Queen(r + 1);                                 }                 }             }               Cols[r] = 0;             return toRet;         }           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             Console.WriteLine($"{Queen(0)}");         }     } }

• Python 3

from sys import stdin, stdout input = stdin.readline print = stdout.write   Arr = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596 ] N = int(input())   print(f'{Arr[N]}')

복기

이전에는 백트래킹 문제를 잘 못 풀었는데, 오늘 풀면서 조금 감을 익힌 것 같다. 백트래킹을 적용해야 하는 문제인지 아닌지를 잘 판별해야 할 것 같다.