[백준 1799번] 비숍 (C/C++)

 

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

1799번: 비숍

---

비숍은 N-Queen 문제와 유사합니다.

비숍의 움직임

비숍은 대각선으로 공격할 수 있기 때문에 배치된 비숍의 대각선으로는 다른 비숍을 배치할 수 없습니다.

따라서 백트래킹 기법을 이용하여 각 대각선마다 하나의 비숍을 배치시키면서 가능한 경우의 수를 모두 수행해봄으로써 체스판 위에 배치할 수 있는 비숍의 개수를 계산할 수 있습니다. (저는 우상향 대각선을 이용하였습니다.)

 

n이 5일 때, 대각선의 개수는 9개입니다. 즉, 2n - 1개입니다.

백트래킹의 끝단에서는 마지막 대각선에 비숍을 배치하므로, 대각선의 개수를 이용하여 재귀를 탈출 할 수 있습니다. 

1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 1

 

n이 5일 때, 각 대각선의 칸의 개수는 아래와 같습니다. 따라서 th번째 대각선의 칸의 개수는 n - |th - (n - 1)|으로 계산할 수 있습니다.

th = 0 -> 1개
th = 1 -> 2개
th = 2 -> 3개
th = 3 -> 4개
th = 4 -> 5개
th = 5 -> 4개
th = 6 -> 3개
th = 7 -> 2개
th = 8 -> 1개
th = 9 -> 0개

 

각 대각선에 위치한 각 칸의 좌표는 아래와 같이 계산할 수 있습니다.

int x = (n - 1 <= th) ? n - 1 - j : th - j; // th번째 대각선의 j번째 위치의 x좌표
int y = (n - 1 <= th) ? th - (n - 1) + j : j;  // th번째 대각선의 j번째 위치의 y좌표

 

아래는 전체 코드입니다. 

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

#define x first
#define y second

int n;  // 체스판의 크기
int board[10][10];  // 체스판
bool isused1[20];   // 우상향 대각선에 대한 상태 배열
bool isused2[20];   // 좌상향 대각선에 대한 상태 배열

int ans = 0;
void bishop(int th, int size){  // th는 우상향 대각선의 index, size는 이전에 선택한 비숍의 개수
    if(th >= 2 * n - 1){    
        ans = max(ans , size); 
    }else{
        bool flag = false;  // th번째 대각선에서 비숍을 놓았는지를 나타내는 flag

        for(int j = 0; j < n - abs(th - (n- 1)); j++){   
            int x = (n - 1 <= th) ? n - 1 - j : th - j;
            int y = (n - 1 <= th) ? th - (n - 1) + j : j;  

            // 비숍을 놓을 수 있으면서, 우상향 대각선과 좌상향 대각선에 비숍이 없는 경우
            if(board[x][y] == 1 && !isused1[th] && !isused2[n - 1 + (x - y)]){  
                flag = true;    
                isused1[th] = true; // 비숍을 놓는 위치에 해당하는 우상향 대각선에 true를 표시
                isused2[n - 1 + (x - y)] = true;    // 좌상향 대각선에 true를 표시
                bishop(th + 1, size + 1); 
                isused1[th] = false;    // 우상향 대각선을 false로 복구
                isused2[n - 1 + (x - y)] = false; // 좌상향 대각선을 false로 복구
            }
        }
        // th 번째 대객선에서 비숍을 놓지 않았다면, size를 늘리지 않고, th + 1번째 비숍을 선택
        if(!flag) bishop(th + 1, size); 
    }

}

int main(){
    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];

    bishop(0, 0);
    cout << ans;
}

아래는 문제 해결에 사용된 테스트케이스입니다.

5
1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 0

3
0 0 0
0 0 0
0 0 0

3
0 0 0
0 0 0
0 0 1

3
0 0 1
0 1 0
0 0 1

10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1