사용한 알고리즘
알고리즘 설명
- 체스판에 대각선의 종류는 두종류 이다.
Case1. 오른쪽 아래 방향의 대각선Case2. 오른쪽 윗 방향의 대각선- 이 두 종류의 대각선으로 보드의 모든 좌표에서 만드는 대각선을 표현할 수 있다.
- 좌표를 (x,y)라고 하면 아래를 모두 만족한다.
Case1. (x+y)가 같은 값이면 하나의 오른쪽 아래 방향의 대각선에 모두 포함 된다.Case2. (N-1-x+y)가 같은 값이면 하나의 오른쪽 윗 방향의 대각선에 모두 포함 된다.- 이를 이용하여 놓을 수 있는 좌표에 하나씩 놓아보며 모두 확인하면 된다.
- 이러한 확인을 DFS를 이용하여 완전 탐색을 진행한다.
- 이 확인 작업은 N이 10이므로 2^(10*10)으로 무작정하면 시간초과를 피할 수 없다.
- 이 때문에 비숍은 체스판의 흰색과 검정색 판을 보았을때 같은 색인 부분만 영향을 미칠 수 있다.
- 이 점을 이용하여 흰색 판에만 비숍을 놓아보고, 검정색 판에만 놓아 보면된다.
- 이를 이용하면 2^(5*5)로 획기적으로 시간을 단축시켜 TLE를 모면할 수 있다.
풀이
// baekjoon 1799 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=11;
int N, board[MAX_N][MAX_N], ans;
// diag[0]: 오른쪽 아래 방향의 대각선들
// diag[1]: 오른쪽 윗 방향의 대각선들
int diag[2][MAX_N*2];
// 이미 비숍이 놓아져 있어 놀수 없는 경우를 판단
inline bool check(int x, int y) {
return !diag[0][x+y] && !diag[1][N-1-x+y];
}
// 대각선 좌표 체크
inline void mark(int x, int y, int value) {
diag[0][x+y]=diag[1][N-1-x+y]=value;
}
int dfs(int x, int y) {
if (x == N) return 0;
int ret = 0;
// x,y 좌표에 놓을수 있는 경우
// 체스판을 보았을때 같은 색깔인 부분만 확인
// 현재 (x,y)좌표에 비숍을 놓고 (x, y+2)좌표 확인하러 가기
// 또는 현재 (x, y)좌표에 비숍을 놓고 (x+1, (y+1)%2) 좌표 확인하러 가기
// 확인 후 다시 x,y 좌표를 지워줌
if (board[x][y] && check(x, y)) {
mark(x, y, 1);
if (y+2 < N) ret = max(ret, dfs(x, y+2) + 1);
else ret = max(ret, dfs(x+1, (y+1)%2) + 1);
mark(x, y, 0);
}
// 현재 (x,y)에 비숍을 놓지 않고 다음을 확인함
// 현재 (x,y)좌표에 비숍을 놓지 않고 (x, y+2)좌표 확인하러 가기
// 또는 현재 (x, y)좌표에 비숍을 놓지 않고 (x+1, (y+1)%2) 좌표 확인하러 가기
if (y+2 < N) ret = max(ret, dfs(x, y+2));
else ret = max(ret, dfs(x+1, (y+1)%2));
return ret;
}
int main() {
scanf("%d", &N);
for (int i=0; i<N; i++)
for (int j=0; j<N; j++)
scanf("%d", &board[i][j]);
ans = dfs(0, 0);
ans += dfs(0, 1);
printf("%d\n", ans);
return 0;
}
