[백준 1799] 비숍 (C#, C++) - soo:bak

문제 링크

1799번 - 비숍

설명

N×N 크기의 체스판이 주어지는 상황에서, N ≤ 10이 주어질 때, 각 칸은 비숍을 놓을 수 있는지 여부가 표시되어 있고 비숍은 대각선으로만 이동한다는 조건 하에 서로 공격하지 않도록 놓을 수 있는 비숍의 최대 개수를 구하는 문제입니다.

비숍은 같은 색 칸에 있는 비숍끼리만 공격할 수 있으므로, 체스판을 흑과 백 두 색으로 분리하여 각각 독립적으로 최대 비숍 수를 구할 수 있습니다.

접근법

체스판을 색으로 분리하여 백트래킹으로 최대 비숍 수를 구합니다.

먼저 체스판을 흑색 칸과 백색 칸으로 나눕니다. 같은 색 칸에 놓인 비숍끼리만 서로 공격할 수 있으므로, 각 색에 대해 독립적으로 백트래킹을 수행합니다.

다음으로 대각선 충돌을 체크하기 위해 두 개의 배열을 사용합니다. 좌하향 대각선은 r + c 값으로, 우하향 대각선은 N - 1 + r - c 값으로 인덱싱합니다.

이후 같은 색 칸만 탐색하기 위해 열을 2씩 건너뛰며 진행하고, 행이 넘어가면 색에 맞게 열 시작 위치를 조정합니다. 비숍을 놓을 수 있는 칸에서 대각선이 비어있으면 비숍을 놓고 재귀하며, 놓지 않는 경우도 탐색하여 최댓값을 갱신합니다.

시간 복잡도는 O(2^(N²/2))입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int n;
    static int[,] board = new int[10, 10];
    static bool[] diagL = new bool[20];
    static bool[] diagR = new bool[20];
    static int[] best = new int[2];

    static void Dfs(int cnt, int r, int c, int color) {
      if (c >= n) {
        c = (c % 2 == 0) ? 1 : 0;
        r++;
      }
      if (r >= n) {
        if (cnt > best[color])
          best[color] = cnt;
        return;
      }

      if (board[r, c] == 1) {
        var dl = r + c;
        var dr = n - 1 + r - c;
        if (!diagL[dl] && !diagR[dr]) {
          diagL[dl] = diagR[dr] = true;
          Dfs(cnt + 1, r, c + 2, color);
          diagL[dl] = diagR[dr] = false;
        }
      }
      Dfs(cnt, r, c + 2, color);
    }

    static void Main(string[] args) {
      n = int.Parse(Console.ReadLine()!);
      for (var i = 0; i < n; i++) {
        var parts = Console.ReadLine()!.Split();
        for (var j = 0; j < n; j++)
          board[i, j] = int.Parse(parts[j]);
      }

      Dfs(0, 0, 0, 0);
      Array.Fill(diagL, false);
      Array.Fill(diagR, false);
      Dfs(0, 0, 1, 1);

      Console.WriteLine(best[0] + best[1]);
    }
  }
}

C++

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

int n;
int board[10][10];
bool diagL[20], diagR[20];
int best[2];

void dfs(int cnt, int r, int c, int color) {
  if (c >= n) {
    c = (c % 2 == 0) ? 1 : 0;
    r++;
  }
  if (r >= n) {
    best[color] = max(best[color], cnt);
    return;
  }

  if (board[r][c]) {
    int dl = r + c;
    int dr = n - 1 + r - c;
    if (!diagL[dl] && !diagR[dr]) {
      diagL[dl] = diagR[dr] = true;
      dfs(cnt + 1, r, c + 2, color);
      diagL[dl] = diagR[dr] = false;
    }
  }
  dfs(cnt, r, c + 2, color);
}

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

  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> board[i][j];

  dfs(0, 0, 0, 0);
  memset(diagL, 0, sizeof(diagL));
  memset(diagR, 0, sizeof(diagR));
  dfs(0, 0, 1, 1);

  cout << best[0] + best[1] << "\n";
  return 0;
}