[백준] Q1799 비숍 JAVA

https://www.acmicpc.net/problem/1799

1799번: 비숍

1. 문제의 유형 및 이해

구현, 백트래킹

N-Queen 문제와 유사하면서도 조건이 달려있는 문제입니다.

N-Queen 문제처럼 놓을 수 있는 곳에 비숍을 놓아가면서 놓을 수 있는지 확인하면서 진행하면 됩니다.

 

Queen 과 달리 비숍의 경우 움직일 수 있는 상태공간은 대각선으로 특정할 수 있습니다.

다만 대각선이라 기존의 n queen 과는 다른 방법으로 가능한지 여부를 체크해 주어야 합니다.

 

 

2. 문제 접근 방법

/ 방향 : x + y 값이 같은 좌표
\ 방향 : y - x 값이 같은 좌표

/ 방향에 대해 0 ~ 2N-2 까지의 대각선을 특정할 수 있고

반대 방향에 대해 -N+1 ~ N-1까지의 대각선을 특정할 수 있습니다.

즉 어떠한 비숍을 (a,b)의 좌표에 놓았을 때 대각선 두개의 위치를 통해 해당 좌표를 특정할 수 있고 각각의 대각선에 가능한 여부를 통해 놓을 수 있는지 없는지 확인할 수 있습니다.

 

또한, 체스 판에 색칠되어 있는 판 모양을 잘 생각해보면 각 색칠한 구간은 서로의 비숍이 절대 닿지 못하는 곳입니다.

해당 부분을 따로 구함으로써 시간을 더욱 줄일 수 있습니다.

 

package solvedac.level5.gold1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author : pcrmcw0486
 * @문제번호 : Q1799
 * @문제이름 : 비숍
 * @난이도 : Gold I
 * @date : 2022-02-28 오후 2:58
 * @문제이해 비숍은 대각선으로 움직일 수 있다.
 * 비숍이 놓일 수 없는 곳이 있다.(놓일순 없지만, 지나갈 수는 있다)
 * 주어진 체스판에서 서로가 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하시오.
 * 체스판의 크기는 10이하. (놓을 수 있다면 1 없다면 0)
 * @알고리즘 10개 이하 많이 놓아봐야 2N-1개
 * @접근방법
 * 체스판에 왜 색칠이 되어있는지 알고 있나?
 */
public class Main {
    static int N;
    static char[][] map;
    static boolean[] LURD;
    static boolean[] RULD;
    static int cnt, ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        LURD = new boolean[2 * N];
        RULD = new boolean[2 * N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine().replaceAll(" ","");
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        ans =0;
        ans = findMaxBishop(0) + findMaxBishop(1);
        System.out.println(ans);
    }

    private static int findMaxBishop(int depth) {
        if (depth >= (2 * N)-1){
            return 0;
        }
        //대각선의 개수 depth 는 2N-1개가 있음.
        // 대각선 idx가 0부터 시작하므로 2N-2까지.
        int x;
        int y;
        int ret =-1;
        //depth는 최대 2N-2 (N-1) = N-1
        for (x = 0; x <= Math.min(depth, N - 1); x++) {
            y = depth - x;
            if(y > N-1) continue;
            if (map[x][y] == '1') {
                if (RULD[x + y] || LURD[y - x + N]) continue;
                RULD[x + y] =  LURD[y - x + N] = true;
                ret = Math.max(ret, findMaxBishop(depth + 2)+1);
                RULD[x + y] = LURD[y - x + N] = false;
            }
        }
        if(ret < 0)
            ret = findMaxBishop(depth + 2);
        return ret;
    }
}