[BOJ] 백준 1799 비숍

 

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int n;
	static boolean[] crossR,crossL;
	static int blackMax,whiteMax;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[][] chess = new int[n][n];
        StringTokenizer st;
        for(int i=0;i<n;i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0;j<n;j++) {
        		chess[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        List<int[]> black = new ArrayList<>();
        List<int[]> white = new ArrayList<>();
        for(int i=0;i<n;i++) {
        	for(int j=0;j<n;j++) {
        		if(chess[i][j]==1) {
        			if((i+j)%2==0) black.add(new int[] {i,j});
        			else white.add(new int[] {i,j});
        		}
        	}
        }
        crossR = new boolean[2*n-1];
        crossL = new boolean[2*n-1];
        blackMax=0; whiteMax=0;
        dfs(black,0,0,true);
        dfs(white,0,0,false);
        System.out.println(blackMax+ whiteMax);
    }
    private static void dfs(List<int[]> list,int idx,int cnt,boolean color) { 
    	if(idx==list.size()) {
    		if(color) blackMax = Math.max(blackMax, cnt);
    		else whiteMax = Math.max(whiteMax, cnt);
    		return;
    	}
    	int[] curr = list.get(idx);
    	int r = curr[0];
    	int c = curr[1];
    	if(!crossR[r+c] && !crossL[r-c+n-1]) {
    		crossR[r+c] = true;
    		crossL[r-c+n-1] = true;
    		if(color) dfs(list,idx+1,cnt+1,color);
    		else dfs(list,idx+1,cnt+1,color);
    		crossR[r+c] = false;
    		crossL[r-c+n-1] = false;
    	}
    	dfs(list,idx+1,cnt,color);
    }
}