[JAVA] 백준 1799 체스

 

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

 

문제분석

정말 불편한 문제다. 시간제한이 10초이지만, 이걸 정직하게 N*N 개의 판 모두를 한번에 탐색하려고 하면 "그 어떤 방법을 쓰더라도" 메모리 초과가 발생한다. 따라서 검은색 판/흰색 판 나누는 것이 필수다. 또한, 대각선에 '무언가 있음' 을 boolean 자료형을 통해 나타낼 수 있어야 한다. 이때 핵심은 비숍의 이동 특성을 정확히 이용하는 것이다. 비숍은 같은 색 칸으로만 이동하므로, 검은 칸에 놓인 비숍은 흰 칸의 비숍과 절대 충돌하지 않는다. 따라서 전체 체스판을 하나의 문제로 보지 않고, 검은 칸과 흰 칸을 각각 독립적인 백트래킹 문제로 나누어 풀어야 한다. 이렇게 하면 탐색 공간이 사실상 절반으로 줄어들고, 시간 안에 해결 가능한 수준으로 내려온다. 이 분리를 하지 않으면 경우의 수가 기하급수적으로 증가해 현실적으로 통과하기 어렵다.

 

또한 대각선 충돌은 r+c와 r−c라는 두 수식으로 완전히 표현할 수 있다. 같은 r+c 값을 가지면 한 방향 대각선에서 충돌하고, 같은 r−c 값을 가지면 반대 방향 대각선에서 충돌한다. 따라서 두 개의 boolean 배열을 만들어 해당 인덱스에 이미 비숍이 놓였는지만 체크하면 된다. 굳이 4방향을 끝까지 탐색할 필요가 없고, 단 한 번의 배열 접근으로 충돌 여부를 판단할 수 있다. 이 부분이 시간 복잡도를 결정짓는 가장 중요한 최적화 포인트다.

 

마지막으로 백트래킹에서는 단순히 “놓는다 / 안 놓는다”를 모두 탐색하는 것이 아니라, 남은 칸 수를 활용한 가지치기가 필요하다. 현재까지 놓은 개수에 앞으로 놓을 수 있는 최대 가능 수를 더해도 이미 구한 최대값을 넘지 못한다면, 그 분기는 더 이상 탐색할 필요가 없다. 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static Set<Integer> set; // row * 10 + col 저장. 여기 저장된 좌표들은 비숍 놓을 수 없음
    static List<Integer> isPos; // row * 10 + col. 비숍 놓을 수 있는 좌표 List
    static boolean[] diag1; // 오른쪽 위로 가는 대각선, row + col 일정, true면 뭔가 있다는 것
    static boolean[] diag2; // 오른쪽 아래로 가는 대각선, row - col + N 일정, true면 뭔가 있다는 것
    static int max = 0;
    static int N;
    static int[] dr = { -1, +1, -1, +1 };
    static int[] dc = { -1, -1, +1, +1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        isPos = new ArrayList<>();
        diag1 = new boolean[2 * N];
        diag2 = new boolean[2 * N];
        set = new HashSet<>();

        ArrayList<Integer> isPosBlack = new ArrayList<>();
        ArrayList<Integer> isPosWhite = new ArrayList<>();

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                if (st.nextToken().equals("1")) {// 1이면 비숍을 놓을 수 있음 -> isPos 좌표 저장
                    if ((i + j) % 2 == 1) {// 흑색 칸
                        isPosBlack.add(i * 10 + j);
                    } else { // 백색 칸
                        isPosWhite.add(i * 10 + j);
                    }
                }
            }
        }
        isPos = isPosWhite;
        backtrack(0, 0);
        int result = max;
        
        max = 0;
        isPos = isPosBlack;
        backtrack(0, 0);
        result += max;

        System.out.println(result);
    }

    // [row][col]에 놓을 수 있나 확인하고 놓을 수 있다면 저장, 안놓는 경우도 무조건 탐색.
    static void backtrack(int count, int idx) {
        if (count + (isPos.size() - idx) <= max)
            return;
        if (idx < isPos.size()) {
            int row = isPos.get(idx) / 10;
            int col = isPos.get(idx) % 10;
            if (!diag1[row + col] && !diag2[row - col + N]) {// idx꺼 놓을 수 있을때, 놓는 상황
                set.add(row * 10 + col);
                diag1[row + col] = true;
                diag2[row - col + N] = true;
                backtrack(count + 1, idx + 1);
                set.remove(row * 10 + col);
                diag1[row + col] = false;
                diag2[row - col + N] = false;
            }
            backtrack(count, idx + 1); // 안놓는 경우도 무조건 탐색해야 함
        } else { // 마지막 idx 넘은 경우
            max = Math.max(max, count);
            return;
        }

    }
}