[백준 1799] 비숍 [C]

백준 - 1799

---

풀이

최악의 경우 모든 체스판의 정보가 1로만 이루어질 때, 시간초과가 발생하기 때문에, 효율적으로 풀이해야 한다.

모든 경우를 고려할 때 시간초과가 발생하는 이유 중 하나는 비숍이 규칙적으로 놓일 수 있는 공간에 대해 생각하지 않기 때문이다.

 

다음처럼 비숍을 놓는 경우를 생각해보자

비숍(빨간원)

즉, 흰색과 회색에 놓일 수 있는 비숍으로 구분해서 탐색한다면 규칙적으로 놓일 수 있는 공간대로 탐색할 수 있다.

입력받은 체스판의 정보에 대해 만약 놓을 수 없는 공간이라면 다음 공간으로 넘어가면 된다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
bool board[11][11], l[19], r[19];
int N, result[2];

void bishop(int row, int col, int cnt, int color){
    if (col >= N){
        col = (col+1)%2;
		
        if (++row == N){
            cnt > result[color] && (result[color] = cnt);
            return;
        }
    }
	
    int lp = (col-row)+N-1, rp = row+col;
    if (board[row][col] && l[lp] + r[rp] == 0){
        l[lp] = r[rp] = true;		
        bishop(row, col + 2, cnt + 1, color);
        l[lp] = r[rp] = false;
    }
	
    bishop(row, col+2, cnt, color);
}
int main(){
    scanf("%d", &N);
    for (int i = 0; i < N*N; i++)
        scanf("%d", &board[i/N][i%N]);
		
    bishop(0, 0, 0, 0);
    bishop(0, 1, 0, 1);
    printf("%d", result[0]+result[1]);
}

---

출처

1799번: 비숍