[Baekjoon] 비숍

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

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

public class Main {
    private static final int PLACEABLE = 1;
    private static boolean[] topLeftCross;
    private static boolean[] topRightCross;
    private static int answer, white, black;
    private static int chessBoardSize;
    private static int[][] chessBoard;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    private static void sol() {
        dfsWhiteTile(0, 0, 0);
        dfsBlackTile(0, 1, 0);

        answer = white + black;
    }

    private static void dfsWhiteTile(int y, int x, int bishopCount) {
        if (y >= chessBoardSize) {
            white = Math.max(white, bishopCount);
            return;
        }

        if (x >= chessBoardSize) {
            dfsWhiteTile(y + 1, (y + 1) % 2 == 0 ? 0 : 1, bishopCount);
            return;
        }

        if (chessBoard[y][x] == PLACEABLE && !topLeftCross[y + x] && !topRightCross[y - x + chessBoardSize - 1]) {
            topLeftCross[y + x] = true;
            topRightCross[y - x + chessBoardSize - 1] = true;

            dfsWhiteTile(y, x + 2, bishopCount + 1);

            topLeftCross[y + x] = false;
            topRightCross[y - x + chessBoardSize - 1] = false;
        }

        dfsWhiteTile(y, x + 2, bishopCount);
    }

    private static void dfsBlackTile(int y, int x, int bishopCount) {
        if (y >= chessBoardSize) {
            black = Math.max(black, bishopCount);
            return;
        }

        if (x >= chessBoardSize) {
            dfsBlackTile(y + 1, (y + 1) % 2 == 0 ? 1 : 0, bishopCount);
            return;
        }

        if (chessBoard[y][x] == PLACEABLE && !topLeftCross[y + x] && !topRightCross[y - x + chessBoardSize - 1]) {
            topLeftCross[y + x] = true;
            topRightCross[y - x + chessBoardSize - 1] = true;

            dfsBlackTile(y, x + 2, bishopCount + 1);

            topLeftCross[y + x] = false;
            topRightCross[y - x + chessBoardSize - 1] = false;
        }

        dfsBlackTile(y, x + 2, bishopCount);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        chessBoardSize = Integer.parseInt(br.readLine());

        chessBoard = new int[chessBoardSize][chessBoardSize];

        StringTokenizer st;

        for (int i = 0; i < chessBoardSize; i++) {

            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < chessBoardSize; j++) {
                chessBoard[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        topLeftCross = new boolean[chessBoardSize * 2];
        topRightCross = new boolean[chessBoardSize * 2];
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• 백트래킹

• DFS

• N-Queen

풀이 방법

• 아주 건전하게(?) 풀었다.

• 흔한 백트래킹 문제같이 새로운 2차원 배열을 생성하고 DFS로 반복해서 메모리 초과를 달성했다.

• N-Queen 문제를 생각해서 대각선 방문 배열을 사용하여 메모리 초과 대신 시간 초과를 달성했다.

  • N-Queen은 대각선, 가로, 세로를 제한하기 때문에 배치할 수 있는 경우의 수가 비숍보다 적어 동일한 로직을 적용할 시 시간초과가 발생한다.

  • 문제에서 제공하는 그림을 생각하지 말고 실제 체스판의 모습을 떠올려본다.

    • 실제 체스판에는 흰색과 검은색 타일이 바둑판 모양으로 되어있다.

    • 검은색 타일에 있는 비숍은 무슨일이 있어도 하얀색 타일에 있는 비숍을 공격할 수 없다.

      • 따라서 검은색 타일 DFS와 하얀색 타일 DFS의 결과가 독립적일 수 있게 된다.

      • Y좌표값의 짝수/홀수에 따라서 좌표 이동만 유의하면 DFS 로직은 동일하다.