[ BOJ ][JAVA][1799] 비숍

www.acmicpc.net/problem/1799

1799번: 비숍

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
10 초	128 MB	12420	2940	1947	23.872%

문제

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

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

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

입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 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

코드

import java.io.*;
import java.util.*;

public class p1799 {
    static int n, answer, maxNum, map[][];
    static boolean[][] visit, colors;
    static int[] res = new int[2]; // black , white
    static int dr[] = {-1, -1};
    static int dc[] = {1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        visit = new boolean[n][n];
        colors = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 체스판 처럼 color check
                colors[i][j] = (i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0);
            }
        }

        // 처음 시작에 비숍을 안 놓는 경우도 체크하기 위해 -1로 시작
        dfs(-1, true, 0);
        dfs(-1, false, 0);
        System.out.println(res[0]+res[1]);
    }
    static void dfs(int index, boolean black, int depth) {
        for (int i = index + 1; i < n * n; i++) {
            int r = i / n;
            int c = i % n;

            if (colors[r][c] != black || map[r][c] == 0 || !check(r, c)) continue;


            visit[r][c] = true;
            dfs(i, black, depth + 1);
            visit[r][c] = false;
        }
        res[black ? 1 : 0] = Math.max(res[black ? 1 : 0], depth);
    }

    static boolean check(int r, int c) {
        // 임의의 순서를 지정해 0, 0부터 시작하므로 아래부분은 비숍이 없다.
        // 따라서 윗 대각선 2개만 체크하면 된다.
        for (int i = 0; i < 2; i++) {
            int nr = r;
            int nc = c;
            while (true) {
                if (OOB(nr, nc)) break;
                if (visit[nr][nc]) return false;

                nr += dr[i];
                nc += dc[i];
            }
        }
        return true;
    }

    static boolean OOB(int r, int c) {
        return r < 0 || r >= n || c < 0 || c >= n;
    }
}