[백준 9663] N-Queen (C#, C++) - soo:bak

문제 링크

9663번 - N-Queen

설명

N×N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 상황에서 N (1 ≤ N < 15)이 주어질 때, 가능한 경우의 수를 구하는 문제입니다.

퀸은 같은 행, 열, 대각선에 있는 퀸을 공격합니다.

접근법

한 행에는 퀸이 최대 하나만 놓이므로 0번째 행부터 각 열에 퀸을 놓아보며 백트래킹을 사용합니다.

i번째 행에 퀸을 놓을 때 이전 행들과 충돌을 검사합니다. 같은 열이면 충돌이고, 대각선은 행 차이와 열 차이의 절댓값이 같으면 충돌입니다.

예를 들어 0번째 행 1번째 열에 퀸이 있을 때 1번째 행에서:

• 열 0: 대각선 충돌 (행 차이 1, 열 차이 1)
• 열 1: 같은 열 충돌
• 열 2: 대각선 충돌 (행 차이 1, 열 차이 1)
• 열 3: 충돌 없음 (행 차이 1, 열 차이 2)

N개 행 모두에 퀸을 배치하면 경우의 수를 1 증가시킵니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int n;
    static int[] col;
    static int answer = 0;

    static void Backtrack(int row) {
      if (row == n) {
        answer++;
        return;
      }

      for (var c = 0; c < n; c++) {
        var ok = true;

        for (var r = 0; r < row; r++) {
          if (col[r] == c || Math.Abs(col[r] - c) == row - r) {
            ok = false;
            break;
          }
        }

        if (!ok) continue;

        col[row] = c;
        Backtrack(row + 1);
      }
    }

    static void Main(string[] args) {
      n = int.Parse(Console.ReadLine()!);
      col = new int[n];

      Backtrack(0);

      Console.WriteLine(answer);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n;
int col[15];
int ans = 0;

void dfs(int row) {
  if (row == n) {
    ans++;
    return;
  }

  for (int c = 0; c < n; c++) {
    bool ok = true;

    for (int r = 0; r < row; r++) {
      if (col[r] == c || abs(col[r] - c) == row - r) {
        ok = false;
        break;
      }
    }

    if (!ok) continue;

    col[row] = c;
    dfs(row + 1);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  dfs(0);
  cout << ans << "\n";

  return 0;
}