문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
코드
#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; } |
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)}"); } } } |
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]}') |
복기
이전에는 백트래킹 문제를 잘 못 풀었는데, 오늘 풀면서 조금 감을 익힌 것 같다. 백트래킹을 적용해야 하는 문제인지 아닌지를 잘 판별해야 할 것 같다.