[BOJ][C/C++] 1799번 : 비숍

🔗링크

1. 문제 풀이

---

만만하게 봤다가 고생한 문제,,

우선 문제를 처음 보았을 때 가장 쉬운 접근법은 백트래킹 방법이다.

비숍을 배치할 수 있는 모든 자리에 대해서 순서대로

1. (i , j)에 비숍을 두고 다음 위치 검사 (i, j에 배치가 가능한 경우)
2. (i , j)에 비숍을 두지 않고 다음 위치 검사
3. 마지막 위치인 경우 이때까지 배치한 비숍 개수 반환

이러한 방식으로 모든 경우를 탐색하는 방법을 생각했다.

1. 모든 경우 검사, 단순한 대각 검사

---

가장 처음에는

[모든 배치 가능한 자리]를 검사하고

[반복문을 이용하여] 비숍의 배치 가능을 검사하였다.

모든 자리 검사

void f(int depth, int n) {
    if (depth == num_pos) { // 모든 자리 검사 시 배치한 비숍의 개수 확인 
        if (res < n)res = n;
        return;
    }
    if (is_able(pos[depth].row, pos[depth].col)) { //배치가 가능하면
          board[pos[depth].row][pos[depth].col] = 1;  // 배치 후 다음자리 검사
          f(depth + 1, n + 1);
          board[pos[depth].row][pos[depth].col] = 0; // 검사 이후 다시 초기화
    }
    f(depth + 1, n); // default = 배치하지 않고 다음 자리 검사
}

배치 가능성 판단 코드

int is_able(int row, int col) {
    int r, c;
    r = row, c = col;
    while (r >= 0 && c >= 0)// 오른쪽 위
        if (board[r--][c--])return 0;
    r = row, c = col;
    while (r >= 0 && c < N) // 왼쪽 위
        if (board[r--][c++])return 0;
    r = row, c = col;
    
    //사실 위에 까지만 해도 검사는 가능하다.
    while (r < N && c >= 0)// 오른쪽 아래
        if (board[r++][c--])return 0;
    r = row, c = col;
    while (r < N && c < N)// 왼쪽 아래
        if (board[r++][c++])return 0;
    return 1;
}

하지만 이 방법은

(배치 가능성 검사에서 대각 검사를 위한 반복문 연산 수) X ($N * N$의 부분집합의 개수인 $2^{N*N}$)

만큼의 시간이 걸림으로 시간초과가 난다

2. 모든 경우 검사, 빠른 대각 검사

---

사실 처음 시간초과를 받았을 땐 대각 검사의 시간 때문인 줄 알았다,,

그래서 반복문이 아닌 수학적인 공식만으로 대각을 검사하는 방법을 사용해 보았다.

만약 비숍을 (4, 5)에 둔다면

왼쪽 : (0, 1)와 (4, 5)를 지나는 직선
오른쪽 : (4, 5)와 (0, 9)를 지나는 직선

을 검사하고

만약 비숍을 (3, 1)에 둔다면

왼쪽 : (2, 0)와 (3, 1)를 지나는 직선
오른쪽 : (1, 3)와 (0, 4)를 지나는 직선

을 검사해야 한다.

즉 (x, y)인 점에 비숍을 배치하면

왼쪽 대각의 경우
x - y ≥ 0 인 경우 : (x - y, 0) 위치에 마킹
x - y < 0 인 경우 : (0, y - x) 위치에 마킹

오른쪽 대각의 경우
(0, x + y) 위치에 마킹

이런식으로 각 대각 모서리에 마킹을 하여 해당 대각이 이미 점유되어 있는지를 검사한다.

int right[19][19], left[19][19];

//a는 마킹을 위한 변수, 1 또는 0
void mark_pos(int row, int col, int a) {
    // 왼쪽 대각
    left[(row - col >= 0) ? row - col : 0][(row - col >= 0) ? 0 : col - row] = a;
    // 오른쪽 대각
    right[0][row + col] = a;
}

하지만 아직 $2^{N*N}$만큼의 경우를 다 검사하기에 시간초과는 해결 되지 않았다.

3. 경우를 나누어 검사, 빠른 대각 검사

---

사실 가장 문제가 되는 것은 $N*N$인 보드에 배치 할수 있는 모든 경우의 수는

$N * N$ 으로 만들수 있는 모든 부분집합인
$2^{N * N}$ 만큼이기에 시간이 너무 오래 걸린다.

그럼 다시 체스판으로 돌아와보자

체스판은 하얀색 칸과 검정색 칸으로 구분된다.
이때 하얀색 칸에 배치된 비숍은 검정색 칸으로 이동할 수 없다.

즉 서로 다른색의 칸에 배치된 비숍들은 서로 영향을 주지 않는다!

그렇기에 모든 경우의 최댓값은

하얀색 칸에서 배치 가능한 최대 비숍 개수
+
검정색 칸에서 배치 가능한 최대 비숍 개수

이 두가지 경우를 구분하여 구한 값을 더한 것과 같고

시간 복잡도 = $O(2^{N/2} + 2^{N/2})$ 만큼의 시간으로
모든 경우를 구할 수 있기에 시간 초과가 나지 않는다!

2. 코드

#include<stdio.h>
typedef struct Pos { int row, col; }Pos;

Pos white[50], black[50];
int N, num_white, num_black;
int right[19][19], left[19][19];

void mark_pos(int row, int col, int a) {
    left[(row - col >= 0) ? row - col : 0][(row - col >= 0) ? 0 : col - row] = a;
    right[0][row + col] = a;
}

int f(int depth, int n, Pos pos[],int max) {
        if (depth == max)return n;
        int row = pos[depth].row, col = pos[depth].col, res1 = 0, res2 = 0;
        if (!left[(row - col >= 0) ? row - col : 0][(row - col >= 0) ? 0 : col - row] && !right[0][row + col]) {
            mark_pos(row, col, 1);
            res1 = f(depth + 1, n + 1,pos,max);
            mark_pos(row, col, 0);
        }
        res2 = f(depth + 1, n, pos,max);
        return (res1 > res2) ? res1 : res2;
}

int main() {
    int input;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            scanf("%d", &input);
            if (input) {
                if ((i + j) % 2 == 0)white[num_white++] = { i,j };
                else black[num_black++] = { i,j };
            }
        }
    printf("%d", f(0, 0, white, num_white) + f(0, 0, black, num_black));
    return 0;
}

3. 후기

시험기간인데 딴짓만 하는 중,,