[백준] 1799번 비숍

문제 설명

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

문제 풀이

• 최적화가 필요한 백트래킹 문제였다.
• 우선 기본적인 알고리즘 개요는 백트래킹으로 이용하여 첫번째 칸부터 마지막까지 둘 것인지 안 둘 것 인지 정하고 가장 큰 값을 구하는 것이다.
• 문제는 시간복잡도인데, 이경우 시간복잡도는 O(2^(N *N))이 되어 시간초과가 발생한다.
• 여기서 중요한 아이디어는 체스판을 2개의 문제로 쪼갤 수 있다는 것이다.
  
• 위 그림에서 흑색칸과 백색칸은 비숍끼리 절대 만날 수 없다.
• 따라서, 흑색칸에 대해 백트래킹, 백색칸에 대해 백트래킹을 진행하고 각 결과를 더해서 결과를 구할 수 있다.
  - 시간복잡도 : O(2^((N/2)*(N/2)))
  - 중요) 보드 크기가 짝수일 경우와 홀수인 경우 칸 증가 방식의 차이가 있다.

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, tmpResult;
    public static int[][] map;
    public static int[] dx = {-1, 1, 1, -1};
    public static int[] dy = {1, 1, -1, -1};

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static boolean isValid(int x, int y) {
        for (int d = 0; d < 4; d++) {
            int amt = 1;
            while(true) {
                int X = x + amt * dx[d];
                int Y = y + amt * dy[d];
                if (X < 0 || Y < 0 || X >= N || Y >= N)
                    break;
                if (map[X][Y] == 2) return false;
                amt++;
            }
        }
        return true;
    }

    public static int calIncr(int ind) {
        //크기가 홀 수일 경우 -> 2증가
        if (N % 2 == 1) return 2;
        //크기가 짝수일 경우
        if (ind % N == N-1) return 1;
        else if (ind % N == N-2) return 3;
        else return 2;
    }

    public static void dfs(int ind, int cnt) {
        if (ind >= N*N) {
            tmpResult = Math.max(tmpResult, cnt);
            return;
        }
        int y = ind % N;
        int x = ind / N;
        int incr = calIncr(ind);

        //0. 둘 수 없는 곳일 경우
        if (map[x][y] == 0) {
            dfs(ind + incr, cnt);
            return;
        }

        //1. 둘 수 있는 곳일 경우
        if (isValid(x, y)) {
            map[x][y] = 2;
            dfs(ind+incr, cnt+1);
            map[x][y] = 1;
        }
        //2. 그냥 안두는 케이스
        dfs(ind+incr, cnt);
    }

    public static void solve() throws IOException {
        int result = 0;
        tmpResult = 0;
        //첫째칸부터 시작할 떄 DFS
        dfs(0, 0);
        result += tmpResult;
        tmpResult = 0;
        //두번째칸부터 시작할 때 DFS
        dfs(1, 0);
        result += tmpResult;
        bw.write(result + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}