[BOJ] 1799번 비숍

복기

체스판 문제는 흑과 백으로 나눠서 생각하도록 하자. 또, 말들의 범위를 검사할 때 메모리를 이용하는 방법도 고려해보자.

코드

• C++ 17

#define _CRT_SECURE_NO_WARNINGS   #include <stdio.h>   #define max(a, b) ((a) > (b) ? (a) : (b))   int N; int Chess[10][10]; int Ans[2];   // 아래 변수는 비숍의 범위가 겹치는지 나타내는 변수다. // 이 값이 1이면 다른 비숍과 범위가 겹쳐 거기에 위치시킬 수 없다. int Left[21];   // 좌하단 방향의 대각선 int Right[21];  // 우하단 방향의 대각선   // 흑과 백을 구분하기 위한 변수 int Criterion;   void dfs(int r, int c, int cnt) {     // 비숍의 개수를 갱신한다.     Ans[Criterion] = max(Ans[Criterion], cnt);       // 다음 행을 검사한다.     if (c >= N)     {         ++r;         // 행이 바뀌면 시작 위치가 달라진다.         c = Criterion ^ (r % 2);     }       // 모든 행을 검사했다면 종료한다.     if (r >= N)         return;       // 해당 위치가 유망한지 확인한다.     if (Chess[r][c] && Left[r + c] == 0 && Right[r - c + N] == 0)     {         Left[r + c] = Right[r - c + N] = 1;         dfs(r, c + 2, cnt + 1);         Left[r + c] = Right[r - c + N] = 0;     }       // 다음 위치를 검사한다.     dfs(r, c + 2, cnt); }   int main() {     scanf("%d", &N);     for (size_t r = 0; r < N; r++)     {         for (size_t c = 0; c < N; c++)             scanf("%d", &Chess[r][c]);     }       // 체스판 중 흑색의 셀을 검사한다.     dfs(0, 0, 0);     Criterion = 1;     // 체스판 중 백색의 셀을 검사한다.     dfs(0, 1, 0);          printf("%d", Ans[0] + Ans[1]); }

• C# 6.0

using System; using System.IO; using System.Text;   namespace Csharp {     class Program     {         static int N = 0;         static int[,] Chess = new int[10, 10];         static int Criterion = 0;         static int[] Left = new int[21];         static int[] Right = new int[21];         static int[] Ans = new int[2];           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             for (int i = 0; i < N; i++)             {                 var inputs = Console.ReadLine().Split();                 for (int j = 0; j < N; j++)                     Chess[i, j] = Convert.ToInt32(inputs[j]);             }               dfs(0, 0, 0);             Criterion = 1;             dfs(0, 1, 0);               Console.Write(Ans[0] + Ans[1]);         }           static void dfs(int r, int c, int cnt)         {             Ans[Criterion] = Math.Max(Ans[Criterion], cnt);               if (c >= N)                 c = Criterion ^ (++r % 2);             if (r >= N)                 return;               if (IsPromising(r, c))             {                 Left[r + c] = Right[r - c + N] = 1;                 dfs(r, c + 2, cnt + 1);                 Left[r + c] = Right[r - c + N] = 0;             }               dfs(r, c + 2, cnt);         }           static bool IsPromising(int r, int c)         {             return (Chess[r, c] == 1 && Left[r + c] == 0 && Right[r - c + N] == 0);         }     } }

• Python 3

from sys import stdin, setrecursionlimit setrecursionlimit(1000000) input = stdin.readline   N = int(input()) Chess = [ list(map(int, input().split())) for _ in range(N)] Count = [0] * 2 Criterion = 0 Left = [0] * 21 Right = [0] * 21      def isPromising(r, c):     if Chess[r][c] and Left[r + c] == 0 and Right[r - c + N] == 0:         return True     else:         return False   def dfs(r, c, count):     Count[Criterion] = max([Count[Criterion], count])          if c >= N:         r += 1         c = Criterion ^ (r % 2)     if r >= N:         return       if isPromising(r, c):         Left[r + c] = Right[r - c + N] = 1         dfs(r, c + 2, count + 1)         Left[r + c] = Right[r - c + N] = 0          dfs(r, c + 2, count)   dfs(0, 0, 0) Criterion = 1 dfs(0, 1, 0)   print(Count[0] + Count[1])