[백준: 1799] 비숍 (Java)

in Devlog on Algorithm, 글또



[1799] 비숍

문제

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

1 < 그림 1 >

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

2 < 그림 2 >

3 < 그림 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방향으로 대각선 이동을 한다는 것이다.

하지만 굳이 비숍의 좌표 기준 상하좌우를 판단 할 필요가 없다. 시간 초과가 나는 가장 큰 이유는 좌표의 상하좌우까지 탐색을 하기 때문.

image-20210829220006975

위 그림처럼 체스판은 흰칸, 검은칸이 나뉘어져 있는데 생각해보면 비숍은 대각선으로만 이동하다 보니 같은 색깔의 칸에만 영향이 간다. 즉 검은칸에 있는 비숍들과 흰칸에 있는 비숍들은 독립적이라는 것이다.

검은 칸과 흰칸을 따로 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;
    }
}

© 2019. by mintheon

Powered by mintheon