백준 1799번 비숍 :: 마이구미

이 글은 백준 알고리즘 문제 1799번 "비숍" 을 풀이한다.

정올 문제로써, 풀이 방법은 DFS 를 통해 해결한다.

문제 링크 - https://www.acmicpc.net/problem/1799

DFS - http://mygumi.tistory.com/102

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. <그림 1>과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. <그림 2>에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 <그림 3>과 같이 최대 7개의 비숍을 놓을 수 있다.  색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

문제는 체스판에 놓을 수 잇는 최대 비숍의 개수를 구해야한다.

비숍은 1인 곳에 놓을 수 있고, 놓는 자리를 기준으로 양 대각선에 비숍이 존재하지 않아야한다.

탐색 문제를 많이 접해봤다면, 모든 경우를 탐색하는 방법을 떠올릴 것이다.

또한, 문제의 시간제한은 특이하게 10초를 준다.

그래서 어떠한 방법을 써도 시간초과를 경험하지는 않을 거라는 느낌이 온다.

단순하게 생각하면 구현 방법은 다음과 같다.

1. 비숍을 놓을 수 있는 곳을 기준으로 DFS + 백트래킹을 활용한다.
2. 그 과정속에서 매번 양 대각선을 확인하면서 탐색한다.

하지만 순수하게 접근할 경우, 시간초과를 경험하게 된다.

시간복잡도 O(2^N*N) 으로 10초를 훨씬 넘게 된다.

모든 체스판의 값이 1일 경우를 생각하면 많은 시간을 요구하게 된다.

시간을 줄일 수 있는 방법은 체스판을 통해 얻을 수 있다.

체스판을 다음 그림을 통해 보자.

체스판을 보다시피 흑백으로 구분할 수 있다.

탐색에 있어서도, 흑백을 구분해서 하면 어떻게 될까?

시간복잡도를 O(2^(N/2 * N/2)) 로 줄일 수 있게 된다.

위와 같이 문제의 성격상 흑백을 구분해서 생각해도 문제되는 것이 없다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2007/1799.java

static int[][] map, colors;
static boolean[] visited = new boolean[100];
static int n;
static int[] ans = new int[2];
static int[] dy = { -1, -1, 1, 1 };
static int[] dx = { -1, 1, 1, -1 };
 
private void solve() {
    n = sc.nextInt();
    map = new int[n][n];
    colors = new int[n][n];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = sc.nextInt();
            if (i % 2 == 0) {
                if (j % 2 == 0) {
                    colors[i][j] = 1;
                }
            } else {
                if (j % 2 != 0) {
                    colors[i][j] = 1;
                }
            }
        }
    }
    dfs(-1, 0, 1);
    dfs(-1, 0, 0);
    System.out.println(ans[0] + ans[1]);
}
 
public static void dfs(int v, int cnt, int color) {
    if (ans[color] < cnt) {
        ans[color] = cnt;
    }
 
    for (int i = v + 1; i < n * n; i++) {
        int c = i / n;
        int r = i % n;
 
        if (colors[c][r] != color) {
            continue;
        }
 
        if (map[c][r] == 1) {
            if (check(c, r)) {
                visited[i] = true;
                dfs(i, cnt + 1, color);
            }
        }
    }
    if (v == -1) return;
    visited[v] = false;
}
 
public static boolean check(int c, int r) {
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + r;
        int ny = dy[i] + c;
        int v = ny * n + nx;
 
        for (int j = 1; j < n; j++) {
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (visited[v]) {
                    return false;
                }
            }
            nx += dx[i];
            ny += dy[i];
            v = ny * n + nx;
        }
    }
    return true;
}