[백준 1799] 비숍

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

이 문제는 백트래킹을 이용하여 풀 수 있습니다. 처음 이 문제를 봤을 때 비숍의 특징을 이용해서 왼쪽 아래 방향으로 이동할 경우 y+x 값이 같은 칸은 비숍을 둘 수 없고 오른쪽 아래 방향으로 이동할 경우 Math.abs(y-x)값이 같은 칸은 비숍을 둘 수 없다는 규칙을 이용해서 매 백트래킹마다 위 반복문을 통해 check 배열을 true 및 false로 세팅하였습니다. 하지만 이 경우 시간 초과가 발생해 다른 해결책을 찾아보아야 합니다.

이 문제는 모든 체스판을 탐색하지 않도록 진행하는 것이 중요합니다. 이를 위해 검정색 이동과 하얀색 이동을 나누어 고려합니다. 즉 기존의 경우 시간 복잡도가 O(N^N)에서 O(2 * (N/2)^(N/2) )로 감소시킬 수 있습니다. 각 칸에서 비숍을 놓을 수 있는지를 체크한 후 존재한다면 값을 1만큼 증가시켜 재귀호출합니다. 이 때 주의할 점은 놓을 수 없어도 비숍을 놓지 않고 넘기는 경우도 존재하므로 현재 개수를 증가시키지 않고 재귀호출하는 부분도 필요합니다. 이 때 검정색과 하얀색은 교차하기 때문에 시작값의 x값을 조정해줍니다. 예를 들어 검정색이 0,0일 경우 그 아랫줄의 검정색은 1,1 , 그 아랫줄의 검정색은 2,0 이 되기 때문에 x값은 시작값에 따라 0 또는 1로 고정됩니다. 이를 파악하여 값을 증가시키고 y가 넘어간다면 함수를 종료한 후 결과값의 합을 출력합니다.

다음은 코드입니다.

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

class Main{
    static int N,blackRes = 0, whiteRes = 0;
    static int[] dy = {-1,-1,1,1}, dx = {1,-1,1,-1};
    static boolean[][] canDo,blackCheck,whiteCheck;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        canDo = new boolean[N][N];

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                int val = Integer.parseInt(st.nextToken());
                canDo[i][j] = val == 1;
            }
        }

        blackCheck = new boolean[N][N];
        blackBacktracking(blackCheck,0,0,0);

        whiteCheck = new boolean[N][N];
        whiteBacktracking(blackCheck,0,1,0);

        System.out.println(blackRes+whiteRes);
    }

    static void blackBacktracking(boolean[][] check, int y, int x, int cnt){
        blackRes = Math.max(blackRes,cnt);

        if(x>=N){
            y++;
            x = (y%2==0) ? 0:1;
        }

        if(y>=N) return;

        if(canPut(check,y,x)){
            check[y][x] = true;
            blackBacktracking(check,y,x+2,cnt+1);
            check[y][x] = false;
        }

        blackBacktracking(check,y,x+2,cnt);
    }

    static void whiteBacktracking(boolean[][] check, int y, int x, int cnt){
        whiteRes = Math.max(whiteRes,cnt);

        if(x>=N){
            y++;
            x = (y%2==0) ? 1:0;
        }

        if(y>=N) return;

        if(canPut(check,y,x)){
            check[y][x] = true;
            whiteBacktracking(check,y,x+2,cnt+1);
            check[y][x] = false;
        }

        whiteBacktracking(check,y,x+2,cnt);
    }

    static boolean canPut(boolean[][] check, int y, int x){
        if(!canDo[y][x]) return false;

        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            for(int j=0;j<N;j++){
                if(ny>=0 && ny<N && nx>=0 && nx<N) {
                    if(check[ny][nx]) return false;

                    ny += dy[i];
                    nx += dx[i];
                }
            }
        }
        return true;
    }
}

참고 자료
https://pangsblog.tistory.com/84