[BOJ] 1799번 비숍

개요

놓을수없는 공간이 존재하고 서로 공격할 수 없는 위치에 비숍을 최대 몇 개까지 배치할 수 있는지 알아내는 문제

문제 링크

코드

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

public class Baekjoon1799 {
    public static final int WHITE = 0;
    public static final int BLACK = 1;
    public static int n;
    public static int[][] board;
    public static int[] crossLeft;
    public static int[] crossRight;
    public static int max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        crossLeft = new int[2*n-1];
        crossRight = new int[2*n-1];
        StringTokenizer st;
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++) 
                board[i][j] = Integer.parseInt(st.nextToken());
        }

        max = 0;
        bishop(0,WHITE,0);  //흰색 블럭 검사
        int whiteMax = max;

        max = 0;
        bishop(0,BLACK,0);  //검은색 블럭 검사
        int blackMax = max;

        bw.write((whiteMax+blackMax)+"");
        bw.flush();
    }

    public static void bishop(int r, int color, int count) {
        for(int i=r;i<n;i++) {
            for(int j=(i%2==color?1:0);j<n;j+=2) {  //체스판 색마다 열의 시작지점 다름
                if(isPromising(i, j)) {
                    board[i][j] = 2;
                    crossLeft[i+j]++;   // '/'대각선 카운트
                    crossRight[i-j+n-1]++;// '\'대각선 카운트
                    bishop(i,color,count+1);
                    crossLeft[i+j]--;
                    crossRight[i-j+n-1]--;
                    board[i][j] = 1;
                }
            }
        }
        if(max < count) //최대 비숍값 갱신
            max = count;
    }

    public static boolean isPromising(int r, int c) {
        if(board[r][c] != 1) 
            return false;   //놓을 수 없는 자리
    
        if(crossLeft[r+c] > 0 || crossRight[r-c+n-1] > 0)   
            return false;   //같은 대각선에 비숍이 있을 때

        return true;
    }
}

해결 과정

N-Queen 문제에서 대각선을 판별했던 방식을 참고해서

비숍이 공격할 수 있는 공간에 있는지 판별했다. ( https://rebas.kr/761 )

위 이미지를 참고해서 대각선 판별에 효율이 좋은 방식을 도입했다.

public static boolean isPromising(int r, int c) {
        if(board[r][c] != 1) 
            return false;   //놓을 수 없는 자리
    
        if(crossLeft[r+c] > 0 || crossRight[r-c+n-1] > 0)   
            return false;   //같은 대각선에 비숍이 있을 때

        return true;
    }

처음엔 한번의 재귀로 모든 칸의 비숍을 판단하는 코드를 작성했지만 시간초과가 났다.

public static void bishop(int count) {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(isPromising(i, j)) {
                    board[i][j] = 2;
                    crossLeft[i+j]++;
                    crossRight[i-j+n-1]++;
                    bishop(count+1);
                    crossLeft[i+j]--;
                    crossRight[i-j+n-1]--;
                    board[i][j] = 1;
                }
            }
        }
        if(max < count) 
            max = count;
    }

그리고 생각해봤을 때 시간복잡도가 엄청나다는 것을 알게 되었다.

n의 최대값인 10을 입력받고 모든 칸에 놓을 수 있다는 최악의 가정에서는

(10 x 10) x (10 x 10) x … x (10 x 10) = 10^20

라는 엄천난 시간복잡도를 보여주었다.

그리고 비숍은 같은 색의 칸만 보면 되는 점을 이용해 검은색 칸, 흰색 칸 따로 탐색을 해주는 방식으로 바꾸어 주었다.

이 때의 시간복잡도는

2 x ( (10 x 5) x (10 x 5) x (10 x 5) x … x (10 x 5) ) = 2 x 10^10 x 5^10 (5^10 ≓ 10^7)

= 2 x 10^17

10^3 만큼의 차이가 나는 것을 확인 할 수 있다.

흰색 칸을 탐색 할 때는 짝수행에서 열이 0부터 시작하고 홀수행에서는 열이 1부터 2칸씩 증가한다.

검은색 칸은 그 반대이다. 이것을 코드로 다음과 같이 구현하였다.

(i%2==color?1:0)

컬러 코드(흰색: 0, 검은색: 1)에 따라 시작지점을 달리해주는 삼항연산자이다.

결과