백준 1799. 비숍 :: 돼지개발자

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

"독립사건을 분할처리해서 시간복잡도를 줄인다."

N-queen 과 유사하게 해당 문제를 풀려고 시도했고, 생각보다 금방 풀리네? 라는 생각을 했다. 하지만 시간 초과... 시간복잡도를 줄여야 한다. 중복 탐색하는 부분은 없었고 어딘가 시간 복잡도를 줄일 방법을 찾아야 했다. 원래 시간복자도는 O(2^(N*N)) 로 제한 시간내에 문제를 풀 수가 없다. 

비숍의 움직임 특성을 보면 4방향 대각선으로만 영향을 끼친다. 즉 아래 체스판을 봤을 때, 같은 색깔의 칸에만 영향을 미친다. 검은칸에 비숍들과 흰 칸의 비숍들은 독립적인 사건인 것이다. 따라서 전체 탐색 범위를 줄여 시간복잡도를 줄이는 방법을 쓴다. O(2^N) 이 될 것 같다. (확실하지 않음;;)

검은 칸을 DFS로 따로 탐색하고 흰 칸을 DFS로 따로 탐색하여 두개 색상에서의 비숍의 최대값을 더해서 답을 찾는다.

문제를 좀더 간단히 하기 위해 배열 좌표 대신 index를 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    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;
    }
}