1799번: 비숍 (BOJ C/C++)

16987번: 계란으로 계란치기

사용 언어: C++

 

문제

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다.  색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

 

풀이

N-Queen: 9663번을 떠올려보면 퀸이 서로 공격할 수 없게 열에 퀸이 있는지, / 방향과 \ 방향에 퀸이 있는지 검사를 했었다.
퀸과 달리 비숍의 특성을 생각해보면 대각선의 방향으로만 움직이고 대각선의 방향으로만 움직이므로 서로 간섭할 수 없는 비숍들이 존재한다.
비숍도 마찬가지로 / 방향과 \ 방향에 비숍이 존재하는지 확인하고 간섭할 수 있는 비숍끼리 (color로 구분) 경우를 둘로 나눠서 답을 더하면 된다.

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

int n;
int ans[2];
bool board[11][11];
bool isused1[20]; // /방향 대각선 비숍 있는지
bool isused2[20]; // \방향 대각선 비숍 있는지

//행, 열, 비숍 개수
//color은 입력받는 색깔이 아닌 기본 체스판의 색깔을 연상하면 된다.
void func(int row, int col, int cnt, int color){
    if(col>=n){
        //열이 n 넘어가면 다음 행으로 넘어감
        row++;
        //1행에서 짝수 열을 검사했다면 2행에서는 홀수 열을 검사함
        if(col%2==0) col=1;
        else col=0;
    }
    if(row==n){
        ans[color] = max(ans[color], cnt);
        return;
    }
    //비숍을 놓을 수 있고 양 대각선에 비숍이 없는 경우
    if(board[row][col] && !isused1[col-row+n-1] && !isused2[col+row]){
        isused1[col-row+n-1] = 1;
        isused2[col+row] = 1;
        func(row, col+2, cnt+1, color);
        isused1[col-row+n-1] = 0;
        isused2[col+row] = 0;    
    }
    //기본 체스판을 생각하면 색깔에 따라 열을 두 개씩 넘어가야함
    func(row, col+2, cnt, color);
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    func(0, 0, 0, 0);
    func(0, 1, 0 ,1);
    cout << ans[0] + ans[1] << '\n';

    return 0;
}