[ 백준 ] 1799 비숍

📌 Problem

비숍 문제는 N-Queens 문제에서 Queen 대신 Bishop을 배치시키는 문제이다. Bishop은 대각선에 있는 다른 bishop을 잡을 수 있다. 그렇기 때문에 Bishop을 배치할 때는 대각선 위치에 다른 bishop을 배치 했는지 먼저 확인해야 한다.

📌 Solution

• 해결 방법
  N-Queen 문제처럼 백트래킹으로 해결할 수 있다. 하지만 시간 복잡도를 고려해야 한다. 체스판의 크기가 최대 10 x 10으로 작고 시간 제한도 10초로 길기 때문에 그냥 백트래킹으로 구현해도 될 것 같지만 사실 시간 제한이 긴 문제일 수록 시간 복잡도를 잘 고려해야한다.

• 시간 복잡도
  이번 문제는 10 x 10의 체스판을 기준으로 생각했을 때 O(10^10)의 시간 복잡도를 가진다. 그런데 체스를 해본 사람은 알겠지만 비숍은 항상 같은 색상에만 위치한다. 체스판은 2가지 색깔이 이웃하지 않게 배치가 되어 있는데 비숍은 대각선으로만 움직이기 때문에 항상 같은 색상에 위치하는 것이다. 즉, 백트래킹을 전체 체스판에 대해서 실행하는 것이 아니라 색상별로 백트래킹을 진행하면 된다. 다시 10 x 10의 체스판을 기준으로 생각해보면 O(5^5*2)의 시간 복잡도를 가지게 된다. 기존의 O(100억)에서 O(6250)로 감소하게 된다.

📌 Code

public class Main {

    private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    private final StringBuilder result = new StringBuilder();

    static class Grid {
        int row, col;
        boolean present;

        public Grid(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public void solve() throws IOException {
        int N = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer;

        List<Grid> blackGrids = new LinkedList<>();
        List<Grid> whiteGrids = new LinkedList<>();

        for (int r = 0; r < N; r++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int c = 0; c < N; c++) {
                if (Integer.parseInt(tokenizer.nextToken()) == 1) {
                    if ((r + c) % 2 == 0) blackGrids.add(new Grid(r, c));
                    else whiteGrids.add(new Grid(r, c));
                }
            }
        }

        int black = search(blackGrids, 0, 0);
        int white = search(whiteGrids, 0, 0);
        result.append(black + white);
    }

    private int search(List<Grid> grids, int index, int count) {
        int maxCount = count;
        loop:
        for (int idx = index; idx < grids.size(); idx++) {
            Grid grid = grids.get(idx);
            for (int g = 0; g < index; g++) {
                Grid preGrid = grids.get(g);
                if (preGrid.present && Math.abs(grid.row - preGrid.row) == Math.abs(grid.col - preGrid.col)) {
                    continue loop;
                }
            }
            grid.present = true;
            maxCount = Math.max(maxCount, search(grids, idx + 1, count + 1));
            grid.present = false;
        }
        return maxCount;
    }

    public void finish() throws IOException {
        writer.write(result.toString());
        writer.flush();
        writer.close();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.solve();
        main.finish();
    }
}