[Algorithm/Java] 백준 1799번 - 비숍

---

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

---

🔍 문제 풀이

문제 도식화

💫 트러블슈팅

처음에는 체스판 전체를 대상으로 DFS를 작성하여 시간 초과가 났다.

10×10 보드에서 놓을 수 있는 칸이 50개라고 하면, 대각선만 겹치지 않게 검사하도록 하여 경우의 수는 2^50개가 되니 당연히 시간 초과가 날 수밖에 없었다.

이후 흑/백 칸을 분리해서 각각 탐색한 뒤 결과를 합치는 방식으로 수정하여 문제를 해결하였다.

흑백으로 나눠 탐색하면 2^W + 2^B만 보면 되어 탐색 공간이 절반으로 줄어든다.

💻 코드

• 흰 칸 (r+c)%2==0인 칸만 따로 DFS -> 최댓값 저장
• 검은 칸 (r+c)%2==1인 칸만 따로 DFS -> 최댓값 저장
• 두 결과를 합쳐서 정답 출력.

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

public class Main {
    static int n;
    static int[][] arr;
    static int ans = 0;
    static boolean[] v1; // ↘
    static boolean[] v2; // ↙

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];

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

        v1 = new boolean[2 * n - 1];
        v2 = new boolean[2 * n - 1];

        dfs(0, 0, 0, 0); // 흰 칸 탐색
        int whiteAns = ans;

        ans = 0;

        dfs(1, 0, 0, 0);
        int blackAns = ans;

        System.out.println(whiteAns + blackAns); // 검은칸 탐색
    }

    private static void dfs(int color, int r, int c, int cnt) {
        // 종료 조건
        if (r >= n) {
            ans = Math.max(ans, cnt);
            return;
        }

        // 열 탐색 끝나면 다음 행으로
        if (c >= n) {
            r++;
            c = 0;
        }

        // 칸이 흑백과 같은 경우 탐색
        if ((r + c) % 2 == color) {
            if (arr[r][c] == 1 && !v1[r + c] && !v2[r - c + n - 1]) {
                v1[r + c] = true;
                v2[r - c + n - 1] = true;

                dfs(color, r, c + 1, cnt + 1); // 비숍 놓기

                v1[r + c] = false;
                v2[r - c + n - 1] = false;
            }
        }

        dfs(color, r, c + 1, cnt); // 비숍 안 놓기
    }
}

초기 코드 (시간초과)

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

public class Main {
    static int n;
    static int[][] arr;
    static int ans = 0;
    static boolean[] v1; // ↘
    static boolean[] v2; // ↙

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];

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

        v1 = new boolean[2 * n - 1];
        v2 = new boolean[2 * n - 1];

        dfs(0, 0);
        System.out.println(ans);
    }

    private static void dfs(int depth, int cnt) {
        if (depth >= n * n) {
            ans = Math.max(ans, cnt);
            return;
        }

        int r = depth / n;
        int c = depth % n;

        // 비숍놓기
        if (arr[r][c] == 1 && !v1[r + c] && !v2[r - c + n - 1]) {
            v1[r + c] = true;
            v2[r - c + n - 1] = true;

            dfs(depth + 1, cnt + 1);

            v1[r + c] = false;
            v2[r - c + n - 1] = false;
        }

        // 비숍 안 놓기
        dfs(depth + 1, cnt);
    }
}