[백준: 1799] 비숍 (Java)
문제
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.
< 그림 1 >
그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.
< 그림 2 >
< 그림 3 >
정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.
입력 1
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 1
출력 1
7
1. 문제 설명
N-Queen
과 비슷한 유형이라서 해당 문제처럼 풀면 시간초과가 난다. $O(2^(N*N))$ 보다 시간복잡도를 줄여야한다.
비숍의 특징은 4방향으로 대각선 이동을 한다는 것이다.
하지만 굳이 비숍의 좌표 기준 상하좌우를 판단 할 필요가 없다. 시간 초과가 나는 가장 큰 이유는 좌표의 상하좌우까지 탐색을 하기 때문.
위 그림처럼 체스판은 흰칸, 검은칸이 나뉘어져 있는데 생각해보면 비숍은 대각선으로만 이동하다 보니 같은 색깔의 칸에만 영향이 간다. 즉 검은칸에 있는 비숍들과 흰칸에 있는 비숍들은 독립적이라는 것이다.
검은 칸과 흰칸을 따로 DFS로 각각 탐색하여 두 색상에서의 비숍 최대값을 더해서 답을 찾는 방식으로 푼다.
정말 생각하기 까다로웠다.. 결국 풀지 못하고 답안지를 봤는데 이렇게 신세계일줄이야.
2. 소스 코드
public class P01799 {
static int n;
static int board[][];
static boolean isVisited[][];
static boolean isBlacked[][];
static int result[];
static int[] dx = {-1, -1};
static int[] dy = {1, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
board = new int[n][n];
isVisited = new boolean[n][n];
isBlacked = new boolean[n][n];
// 0은 검정칸, 1은 흰칸의 max값
result = new int[2];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
//검정색 칸 생성처리
isBlacked[i][j] = (i % 2 != 0 && j % 2 != 0) || i % 2 == 0 && j % 2 == 0;
}
}
//검정칸 탐색
search(-1, true, 0);
//흰칸 탐색
search(-1, false, 0);
System.out.println(result[0] + result[1]);
}
private static void search(int index, boolean isSearchBlack, int count) {
for (int i = index + 1; i < n * n; i++) {
int x = i / n;
int y = i % n;
// 현재 탐색중인 색이 아니거나, 비숍을 놓을 수 없거나, 대각선에 비숍이 존재하거나
if (isBlacked[x][y] != isSearchBlack || board[x][y] == 0 || !isValid(x, y)) {
continue;
}
isVisited[x][y] = true;
search(i, isSearchBlack, count + 1);
isVisited[x][y] = false;
}
int resultIndex = isSearchBlack ? 0 : 1;
result[resultIndex] = Math.max(result[resultIndex], count);
}
private static boolean isValid(int x, int y) {
// 좌측 하단부터 우측 하단순으로 탐색하므로 윗 대각선의 비숍만 체크한다.
for (int i = 0; i < 2; i++) {
int xx = x;
int yy = y;
while (true) {
if (xx >= n || yy >= n || xx < 0 || yy < 0) {
break;
}
if (isVisited[xx][yy]) {
return false;
}
xx += dx[i];
yy += dy[i];
}
}
return true;
}
}