[BOJ] 백준 1799 - 비숍

백준 1799 - 비숍

---

체스판이 주어졌을 때 비숍은 대각선에 있는 다른 비숍을 잡을 수 있다고 합니다

구해야하는 값은 비숍들이 서로를 잡을 수 없도록 하여 체스판 위에 최대로 놓을 수 있는 비숍의 개수를 구하는 문제입니다.

N-queen 처럼 백트래킹을 쓰면 쉽게 구현할 수 있을 것 같았지만, 

만약 10 x 10 에서 모든 자리가 1로 채워져 모든 자리에 비숍을 놓을 수 있다고 하면 10초안에는 절대로 구할 수 없게됩니다.

따라서 백트래킹을 들어가기 전에 몇가지 경우를 나누어주어야 합니다.

먼저, 체스판을 보게되면 흰색과 검정색으로 나뉘어진 부분을 볼 수 있습니다. (위의 체스판이 아닌 아래의 체스판을 참고해야 합니다.)

검정색 판에 비숍이 놓이게 되면 아래와 같이 흰색 부분에 놓인 비숍은 대각선 위에 위치하지 않으며 따라서 절대 잡을 수 없게 됩니다.

따라서 먼저 나눌 수 있는 경우

1. 검정색 판에 놓이는 비숍과 흰색 판에 놓이는 비숍

또한, 0이 적힌 곳에는 비숍을 놓을 수 없으므로, 

다음 1을 찾아서 가는 것보다 1인 부분의 좌표를 따로 저장해 배열을 만들어 저장해준 다음 해당 배열을 백트래킹하는 것이 효율적이라 판단했습니다.

2. 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의 좌표의 배열은 {(0,0), (0,4), (1, 1), (2,0), (2, 2), (2, 4), ... }

흰색 판의 1의 좌표의 배열은 {(0,1), (0, 3), (3, 0), ... } 이 됩니다.

즉, 검정색 판은 N(i,j) 에서 i+j%2 == 0 일 때, 흰색 판은 (i+j)%2 == 0 일 때가 됩니다.

위의 경우를 나누어 백트래킹을 진행한 코드는 다음과 같습니다.

import java.util.ArrayList;
import java.util.Scanner;
 
/*
 * 체스판이 다음과 같다고 하면,
 * | * * * *
 * | * * * *
 * | * * * *
 * | * * * *
 * 대각선에 올 수 없다는 뜻은 다음과 같다.
 * | *   *      |   *   *
 * |   *   * | *   *
 * | *   *   |   *   *
 * |   *   * | *   *
 * 왼쪽 칸에 있는 비숍들은 오른쪽 칸의 비숍과 대각선 관계에 없다.
 * 마찬가지로, 오른쪽 칸에 있는 비숍들은 왼쪽 칸의 비숍과 대각선 관계에 없다.
 * 즉, 왼쪽 칸에서의 최대 비숍과 오른쪽 칸의 최대 비숍의 수를 더하면 최대의 비숍의 수가 된다.
 */
 
public class Main {
    
    static int lAns = 0;
    static int rAns = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<int[]> lMap = new ArrayList<int[]>(); // 대각선에서 나올 수 있는 판 
        ArrayList<int[]> rMap = new ArrayList<int[]>();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                int can = sc.nextInt();
                if(can == 1) {
                    int[] input = {i, j};
                    if((i+j)%2 == 0) // 왼쪽 맵의 비숍
                        lMap.add(input);
                    else 
                        rMap.add(input);
                }
            }
        }
        boolean[] lvisit = new boolean[lMap.size()];
        boolean[] rvisit = new boolean[rMap.size()];
        
        lbfs(lMap, lvisit, 0, 0);
        rbfs(rMap, rvisit, 0, 0);
        
        System.out.println(rAns + lAns);
    }
 
    private static void lbfs(ArrayList<int[]> map, boolean[] visit, int n, int cnt) {
        // TODO Auto-generated method stub
        
        if(n >= map.size()) {
            lAns = lAns < cnt ? cnt : lAns;
            return;
        }
        
        if(cnt + (map.size() - n + 1) < lAns) return;
        
        for(int i=n; i<map.size(); i++) {
            if(isNotDiagonal(map, visit, i)) {
                visit[i] = true;
                lbfs(map, visit, i+1, cnt+1);
                visit[i] = false;
            }
        }
        
        lAns = lAns < cnt ? cnt : lAns;
    }
    
    private static void rbfs(ArrayList<int[]> map, boolean[] visit, int n, int cnt) {
        // TODO Auto-generated method stub
        
        if(n >= map.size()) {
            rAns = rAns < cnt ? cnt : rAns;
            return;
        }
        
        if(cnt + (map.size() - n + 1) < rAns) return;
        
        for(int i=n; i<map.size(); i++) {
            if(isNotDiagonal(map, visit, i)) {
                visit[i] = true;
                rbfs(map, visit, i+1, cnt+1);
                visit[i] = false;
            }
        }
        
        rAns = rAns < cnt ? cnt : rAns;
    }
 
    private static boolean isNotDiagonal(ArrayList<int[]> map, boolean[] visit, int n) {
        int[] a = map.get(n);
        
        for(int i=0; i<n; i++) {
            if(visit[i]) {
                int[] b = map.get(i);
                if(Math.abs(a[0] - b[0]) == Math.abs(a[1] - b[1])) { // 대각선에 있는 경우.
                    return false;
                }
            }
        }
        
        return true;
    }
 
    
}