[백준 1799] 비숍 / 자바 / 백트래킹 + 분할정복

#문제

레벨: G1
알고리즘: 백트래킹 + 분할정복
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이

완전탐색을 할 경우 2의 100승으로 무조건 시간초과입니다. 그렇다 하면 조금 더 긍정적으로 생각해보겠습니다. 흰색칸 비숍과 검정칸 비숍은 서로 영향을 줄 수 없습니다. 그래서 우린 흰색칸 비숍과 검정칸 비숍을 나누어서 탐색하게 된다면
2^50 + 2^50 으로 아까보다 나아졌습니다. 그래도 우린 시간초과에 걸립니다. 그렇다면 우리에겐 dp가 남아있습니다. 위 문제를 dp로 풀 경우를 생각하면 비트마스킹 dp을 생각해볼 수 있습니다. 이차원배열을 100자리의 비트마스킹으로 표현하는 것입니다. 그러나 대각선의 겹치는 비숍이 있는지 검사하기에는 까다로울 것 같습니다. 또한 2^50 길이의 배열을 두 개 생성하여 하므로 메모리 초과가 날 것 같습니다.

돌아와서 남은 방법은 완전탐색 입니다. 시간복잡도가 10초이고, 1인 칸만 탐색하면기 때문에 약간의 희망은 있습니다. 완전탐색의 최악의 시간복잡도는 2^50 + 2^50입니다. 그래도 다른 방법이 없으니 시도 한 번 해보겠습니다.

이 문제에 다른 블로그를 보면 위 문제는 빽트래킹이라고 설명합니다. 빽트래킹의 정의는 조건에 일치하지 않는다면 해당 재귀를 멈추는 것입니다. 그러나 제 코드, 다른 코드를 보더라도 재귀를 멈추는 코드는 없습니다. 단지, 비숍을 안 놓더라도 재귀는 계속됩니다. 개념은 중요하기 때문에 이렇게 짚고 넘어갑니다!

---

#풀이 코드

import java.util.*;

public class Main {
    static int N;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {-1, -1};  // 대각선 방향 (왼쪽 위, 오른쪽 위)
    static int[] dy = {-1, 1};   // 대각선 방향 (왼쪽 위, 오른쪽 위)
    static int maxBlack = 0, maxWhite = 0;

    // 현재 대각선에서 비숍을 놓을 수 있는지 체크
    static boolean canPlaceBishop(int x, int y) {
        for (int i = 0; i < 2; i++) {
            int nx = x, ny = y;
            while (true) {
                nx += dx[i];
                ny += dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) break;
                if (visited[nx][ny]) return false;
            }
        }
        return true;
    }

    // 백트래킹을 이용한 비숍 배치
    static void placeBishop(int x, int y, int count, boolean isBlack) {
        if (x >= N) {
            if (isBlack) maxBlack = Math.max(maxBlack, count);
            else maxWhite = Math.max(maxWhite, count);
            return;
        }

        int nx = x, ny = y + 2;  // 같은 색깔만 고려 (칸을 건너뛴다)
        if (ny >= N) {  // 다음 줄로 넘어간다
            nx++;
            ny = (y % 2 == 0) ? 1 : 0;  // 홀수 칸 또는 짝수 칸 시작
        }

        // 비숍을 놓을 수 있으면 놓고 다음 단계로
        if (board[x][y] == 1 && canPlaceBishop(x, y)) {
            visited[x][y] = true;
            placeBishop(nx, ny, count + 1, isBlack);
            visited[x][y] = false;
        }

        // 비숍을 놓지 않고 다음 단계로
        placeBishop(nx, ny, count, isBlack);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        board = new int[N][N];
        visited = new boolean[N][N];

        // 체스판 정보 입력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        // 흑 칸 (black diagonal) 백트래킹
        placeBishop(0, 0, 0, true);

        // 백 칸 (white diagonal) 백트래킹
        placeBishop(0, 1, 0, false);

        // 흑 + 백 칸에서의 비숍 최대 개수 출력
        System.out.println(maxBlack + maxWhite);
    }
}