[백준 1799] - [백트래킹] - 비숍 (JAVA)

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

---

이 문제는 이전에 풀었던 N-Queen 문제의 확장판 문제이다.

2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen

그리고 백트래킹 문제의 최고존엄 문제 급이지 않을까 생각한다.

이 문제를 잘못 접근하게 되면 문제는 풀겠지만 시간 초과에 걸리게 된다. 

잘못접근하는 대부분의 이슈는 하나의 체스판을 전체 탐색을 할경우 생기게 된다. 

비숍은 대각선으로 움직인다. 그렇다면 대각선에는 비숍이 위치할 수 없다.

아래처럼 2,2 에 비숍이 위치할 경우 대각선에 위치한 모든 좌표에는 비숍을 놓을 수 없다.

	B

또 여기서 하나 중요하게 고려해야할게 있는데 2, 2에 비숍을 놓았을경우 비숍의 좌표 기준 상, 하, 좌, 우 는 비숍을 놓을 수 있는지 탐색할 필요가 없다.

즉 시간초과가 나는 가장 큰 이유는 (y, x) 좌표에 비숍을 놓을 경우 상,하,좌,우 까지 같이 탐색을 하기 때문이다.

체스판은 흑색 칸과 백색 칸이 있고 이 칸들은 한칸 건너서 위치한다.

흑색과 백색 칸은 서로에게 영향을 주지 않는다.

즉 탐색 자체를 흑색칸에 비숍을 놓았을 경우 흑색 칸에 대한 탐색만 하고 백색칸에 비숍을 놓았을 경우 백색칸에 대한 탐색을 진행한 다음 두번의 탐색에 걸쳐 나온 비숍을 놓을 수 있는 자리수를 더해서 출력하면 되는 문제이다. 

흑색칸은 (1, 1) 부터 탐색을 진행했고

백색칸은 (1,2) 부터 탐색을 진행했다.

x의 좌표를 2씩 증가 시키면서 같은 색의 칸을 탐색하게 했고 x 의 좌표가 체스의 크기보다 켜질 경우 

y 좌표를 1씩 증가 시키고 x 좌표는 y 좌표에 따라서 초기화 해줬다. 

해당 좌표에 비숍을 놓을 수 있는지에 대한 탐색 자체도 상하좌우에 대각선까지 탐색하지 않고 비숍 기준 대각선으로만 탐색을 진해하여 시간 초과를 방지했다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int size;
    public static int[][] chess;
    
    public static int[] dy = {-1, -1, 1, 1}; // 좌상, 우상, 좌하, 우하
    public static int[] dx = {-1, 1, -1, 1}; // 좌상, 우상, 좌하, 우하
    
    public static int b_cnt = 0;
    public static int w_cnt = 0;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        size = Integer.parseInt(br.readLine());
        
        chess = new int[size+1][size+1];
        
        // 입력
        for(int i=1; i <= size; i++) {
            st = new StringTokenizer(br.readLine());
            
            for(int j=1; j <= size; j++) {
                chess[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 흑색 자리에 둘 수 있는 비숍의 수를 탐색한다.
        boolean[][] black_visited = new boolean[size+1][size+1];
        black_search(black_visited, 1, 1, 0);
        
        // 백색 자리에 둘 수 있는 비숍의 수를 탐색한다.
        boolean[][] white_visited = new boolean[size+1][size+1];
        white_search(white_visited, 1, 2, 0);
        
        // 흑색, 백색 자리에 둘 수 있는 비숍의 수를 합하여 출력한다.
        System.out.println(b_cnt+w_cnt);
    }
 
    public static void black_search(boolean[][] visited, int y, int x, int cnt) {
        // 검은자리에 둘 수 있는 횟수가 기존 횟수보다 크면 값을 변경한다.
        b_cnt = Math.max(cnt, b_cnt);
        
        // x 표가 체스판의 크기보다 크면 좌표를 다음칸의 첫번째 x 좌표로 이동 시켜준다.
        // 단, 흑색 자리는 y가 홀수일 경우 x의 시작 점이 1부터 시작되고
        //    짝수일 경우 2부터 시작된다.
        if(x > size) {
            y += 1;
            x = (y%2 == 0)?2:1;
        }
        
        // y의 좌표가 체스판의 사이즈를 초과할경우 탐색을 종료한다.
        if(y > size) return;
        
        
        // 현재자리에 비숍을 놓을 수 있는지 확인
        // 현재자리에 비숍을 놓을 수 있다면 비숍을 놓고 다음 탐색을 진행한다.
        // 다음 탐색을 진행할 때에는 x좌표를 2증가 시켜줘야 한다. 이유는 옆 자리는 색이 다른 자리니깐
        // 비숍을 둘 경우에는 cnt를 1 증가 시켜줘야한다.
        if(isAble(visited, y, x)) {
            visited[y][x] = true;
            black_search(visited, y, x+2, cnt+1);
            visited[y][x] = false;
        }
        
        // 현재자리에 비숍을 놓을수 있더라도 안놓을수도 있기 때문에 비숍을 놓지 않았을 경우에 대한 탐색도 진행한다.
        // 다음 탐색을 진행할 때에는 x좌표를 2증가 시켜줘야 한다. 이유는 옆 자리는 색이 다른 자리니깐
        // 비숍을 놓지 않았을 경우에는 cnt를 증가시킬 필요가 없다.
        black_search(visited, y, x+2, cnt);
    }
    
    public static void white_search(boolean[][] visited, int y, int x, int cnt) {
        // 백색 자리에 둘 수 있는 횟수가 기존 횟수보다 크면 값을 변경한다.
        w_cnt = Math.max(cnt, w_cnt);
        
        // x 표가 체스판의 크기보다 크면 좌표를 다음칸의 첫번째 x 좌표로 이동 시켜준다.
        // 단, 백색 자리는 y가 홀수일 경우 x의 시작 점이 2부터 시작되고
        //    짝수일 경우 1부터 시작된다.
        if(x > size) {
            y += 1;
            x = (y%2 == 0)?1:2;
        }
        
        // y의 좌표가 체스판의 사이즈를 초과할경우 탐색을 종료한다.
        if(y > size) return;
        
        // 현재자리에 비숍을 놓을 수 있는지 확인
        // 현재자리에 비숍을 놓을 수 있다면 비숍을 놓고 다음 탐색을 진행한다.
        // 다음 탐색을 진행할 때에는 x좌표를 2증가 시켜줘야 한다. 이유는 옆 자리는 색이 다른 자리니깐
        // 비숍을 둘 경우에는 cnt를 1 증가 시켜줘야한다.
        if(isAble(visited, y, x)) {
            visited[y][x] = true;
            white_search(visited, y, x+2, cnt+1);
            visited[y][x] = false;
        }
        
        // 현재자리에 비숍을 놓을수 있더라도 안놓을수도 있기 때문에 비숍을 놓지 않았을 경우에 대한 탐색도 진행한다.
        // 다음 탐색을 진행할 때에는 x좌표를 2증가 시켜줘야 한다. 이유는 옆 자리는 색이 다른 자리니깐
        // 비숍을 놓지 않았을 경우에는 cnt를 증가시킬 필요가 없다.
        white_search(visited, y, x+2, cnt);
    }
    
    
    public static boolean isAble(boolean[][] visited, int y, int x) {
        if(chess[y][x] == 0) return false; // 0이면 놓을 수 없다.
        
        for(int i=0; i < 4; i ++) {
            int yy = dy[i] + y;
            int xx = dx[i] + x;
            
            for(int j=1; j <= size; j++) {
                if(yy > 0 && xx > 0 && yy <= size && xx <= size) {
                    if(visited[yy][xx]) return false;
                    
                    yy += dy[i];
                    xx += dx[i];
                }
            }
        }
        return true;
    }
}