[백준 1799번] 비숍

문제 링크: https://www.acmicpc.net/problem/1799

1799번: 비숍

 

 

<문제 풀이> 백트랙킹

 https://www.acmicpc.net/problem/9663

9663번: N-Queen

이문제는 9663번 문제와 비슷하게 접근하면 되는데 핵심은 다음 세 가지입니다.

1. 체스판은 흑색, 백색으로 나누어져 있고, 각 비숍은 다른 색깔에 위치한 비숍을 공격할 수 없다.

 

2. 2차원 배열에서 조합

 

3. 2차원 배열에서 윗 방향 대각선은 X + Y, 아랫 방향 대각선은 X - Y + N으로 나타낼 수 있다.

 

흰색, 검은색 판을 구분하는 방법은 2차원 배열에서 x + y 값을 보면 같은 대각선에 존재하면 x +  y 값이 같은 걸 알 수 있습니다. 

 

 

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
int board[10][10];
bool visited1[20]; //  / 대각선
bool visited2[20]; //  \ 대각선
int n;
int res = 0;
void dfs(int k, int cnt, bool color) { //color == true 흰색, color == false 검은색
    if (k >= n * n) {
        return;
    }
    for (int i = k; i < n * n; i++) {
        int x = i / n;
        int y = i % n;
        if (color && (x + y) % 2 != 0) {//흰색이 아니면
            continue;
        }
        else if(!color && (x + y) % 2 == 0){//검은색이 아니면
            continue;
        }
        if (board[x][y] == 0) continue;
        if (visited1[x + y])continue;
        if (visited2[x - y + n])continue;
        visited1[x + y] = true;
        visited2[x - y + n] = true;
        res = max(res, cnt + 1);
        dfs(i + 1 , cnt + 1, color);
        visited1[x + y] = false;
        visited2[x - y + n] = false;
        
    }
}
int main(void) {
    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, true);
    int temp = res;
    res = 0;
    dfs(1, 0, false);
    cout << temp + res;
    return 0;
}