b1799. 비숍

 

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

 

 

 

이 문제는 N×N 체스판에서 비숍을 놓을 수 있는 최대 개수를 구하는 문제다.

비숍은 대각선으로 이동하며 공격 범위를 가지기 때문에,
서로 공격 범위가 겹치지 않도록 배치해야 한다.

체스판은 흑백 칸으로 나뉘기 때문에,
흑색 칸과 백색 칸을 따로 탐색하여 각각의 최대 비숍 수를 구하고
이를 합산하는 방식으로 진행된다.

입력으로 체스판 크기 NNN과 각 칸에 비숍을 놓을 수 있는지 여부를 나타내는 map 배열을 생성한다.
이후 dfs 메서드를 호출하여 흑색 칸은 (0,0)에서 시작,
백색 칸은 (1,0)에서 시작해 탐색한다.
dfs는 현재 위치에 비숍을 놓는 경우와 놓지 않는 경우를 모두 탐색하며,
놓을 수 있는 경우에는 visited 배열에 표시하고 다음 칸으로 이동한다.
탐색이 끝난 후에는 visited를 초기화해
다른 경우의 탐색에 영향을 주지 않도록 백트래킹을 수행한다.
비숍을 놓을 수 있는지 여부는 check 메서드를 통해 판단하며,
대각선 4방향으로 이미 비숍이 놓인 칸이 있는지 확인한다.
놓을 수 없는 칸이면 다음 칸으로 이동하며 탐색을 계속한다.
탐색 과정에서 흑색과 백색 각각의 최대 비숍 수를 bMax와 wMax에 기록하며,
최종적으로 두 값을 합산해 출력한다.

이 코드는 체스판의 흑백 특성을 활용해 계산량을 절반으로 줄였으며, DFS와 백트래킹으로 최적의 비숍 배치를 찾는 구조다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int N, bMax, wMax;
    private static int[][] map;

    private static int[] dx = {-1, 1, -1, 1};
    private static int[] dy = {-1, -1, 1, 1};

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

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        bMax = 0;
        wMax = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(new boolean[N][N], 0, 0, 0, true); // 흑색 탐색
        dfs(new boolean[N][N], 1, 0, 0, false); // 백색 탐색

        System.out.println(bMax + wMax);
    }

    private static void dfs(boolean[][] visited, int x, int y, int sum, boolean isBlack) {
        if (isBlack) {
            bMax = Math.max(bMax, sum);
        } else {
            wMax = Math.max(wMax, sum);
        }

        if (x >= N) {
            y += 1;
            x = (y % 2 == 0) ? (isBlack ? 0 : 1) : (isBlack ? 1 : 0);
        }

        if (y >= N) return;

        if (check(visited, y, x)) {
            visited[y][x] = true;
            dfs(visited, x + 2, y, sum + 1, isBlack); // 비숍을 놓는 경우
            visited[y][x] = false;
        }
        dfs(visited, x + 2, y, sum, isBlack); // 비숍을 놓지 않는 경우
    }

    private static boolean check(boolean[][] visited, int y, int x) {
        if (map[y][x] == 0) return false; // 비숍을 놓을 수 없는 자리

        for (int i = 0; i < 4; i++) {
            int yy = y, xx = x;

            while (true) { // 대각선 끝까지 탐색
                yy += dy[i];
                xx += dx[i];

                if (yy < 0 || xx < 0 || yy >= N || xx >= N) break;
                if (visited[yy][xx]) return false;
            }
        }
        return true;
    }
}