비숍 [백준 1799][JAVA][골드2][백트래킹]

 

[광고 누르면 오늘의 행운 상승!!]

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

1799번: 비숍

1. 주의할점
짝수줄과 홀수줄의 비숍은 절대로 만날 수 없다. 서로를 구분하여 구현한다.

2. 구현
- 2차원 배열을 1차원으로 변환하여 노드를 탐색한다.
- 현재 탐색중인 색이 아니거나 놓을 수 없거나 대각선에 비숍이 존재하면 continue
- 대각선에 비숍이 있는지 검사하는 방법은 check함수를 이용하여 위쪽 대각선만 검사하였다. 
- 짝수줄과 홀수줄의 결과값을 더하여 출력한다.

package Study5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class 비숍2 {
 
    static int n;
    static int[][] map;
    static boolean[][] colors;
    static boolean[][] visited;
    static int[] res = new int[2];    // black , white
    static int[] dx = {-1,-1};
    static int[] dy = {1,-1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        map = new int[n][n];
        colors = new boolean[n][n];
        visited = new boolean[n][n];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 체스판 처럼 colors check
                colors[i][j] = (i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0); 
            }
        }
        // 처음 시작에 비숍을 안놓는 경우를 체크하기위해 -1 대입.
        solve(-1,true,0);
        solve(-1,false,0);
        
        System.out.println(res[0]+res[1]);
    }
    
    static void solve(int index, boolean black, int cnt) {
        // 다음 노드부터 탐색
        for (int i = index+1; i < n*n; i++) {
            int x = i / n;
            int y = i % n;
            
            // 현재 탐색중인 색이 아니거나, 놓을 수 없거나, 대각선에 비숍이 존재하거나
            if(colors[x][y] != black || map[x][y] == 0 || !check(x,y)) 
                continue;
            
            // 백트래킹
            visited[x][y] = true;
            solve(i,black, cnt+1);
            visited[x][y] = false;
        }
        res[black ? 1 : 0] = Math.max(res[black ? 1 : 0], cnt);
    }
    
    static boolean check(int x, int y) {
        // 임의의 순서를 지정해 0,0 부터 시작하므로 아래부분에는 비숍이 없다.
        // 따라서, 윗 대각선만 체크한다.
        for (int i = 0; i < 2; i++) {
            int nx = x;
            int ny = y;
            while(true) {
                if(nx < 0 || nx >= n || ny < 0 || ny >= n)
                    break;
                if(visited[nx][ny])
                    return false;
                nx += dx[i];
                ny += dy[i];
            }
        }
        return true;
    }
}