[Dev-Ping9] 백준 1018번 - 체스판 다시 칠하기 (Java)

 

# 문제 설명

 N과 M이 50보다 작으며, 시간제한은 2초라 그냥 손에 잡히는대로 풀면 풀리는 문제

 

 

# 수행시간

 단순 무식하게 접근 했을 때, 8X8 의 비교연산을 (N-7)X(M-7) 번 한다. (그냥 구현만 제대로하면 된다는 뜻)  

 

 허나 N과 M의 범위가 커질때를 대비하여 더 나은 성능에 대한 고민을 해보았다.

 

 [1X8 블록]을 만들어 옮기면서 비교하면, 추가되는 원소에 대한 비교만 해주면 되기때문에 비교연산이 1X(N-7)X(M-7) 로 줄어드나

 Big-O 표기법으로 봤을 때 아무 의미 없을 것이다. 

 

 그래서 아무 걱정없이 문제가 시키는대로 구현하기로 했다. 

 

 

 

# 코드구현

백준(맞힌사람)에서 Java 11 로 검색해서 높은순위에 공개된 코드에는 나처럼 board를 만들지 않는다...

boolean 변수 하나로 board를 대신한다... (너무 섹시한 것 같다...)

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

public class Main{
    static char[][][] board = new char[2][8][8];
    static char[][] givenBoard;

    static int getDifferentCount(char[][] given,int givenI, int givenJ){
        int boardI=0; int boardJ=0;
        int cnt_0 = 0; int cnt_1=0;
        
        for(int i=givenI;i<8+givenI;i++){
            for(int j=givenJ;j<8+givenJ;j++){
                if(board[0][boardI][boardJ]!= given[i][j]){
                    cnt_0++;
                }
                if(board[1][boardI][boardJ]!= given[i][j]){
                    cnt_1++;
                }
                boardJ++;
            }
            boardJ=0;
            boardI++;
        }
        return Math.min(cnt_0, cnt_1); // == Math.min(cnt_0, 64-cnt_0); wow....
    }

    public static void main(String[] args) throws IOException{
        // 8<= m , n <=50
        // 8x8 로 자름 
        // 칠해야되는 정사각형 최소가 되게
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        givenBoard = new char[n][m];
        for(int i=0;i<n;i++){
            givenBoard[i] = br.readLine().toCharArray();
        }

        //make target board (=> 만들필요없이 true false 로 계속 반전시키면 되는거였음 ㅠㅠ..)
        int flag=0;
        for(int i=0; i<8;i++){
            for(int j=0; j<8;j++){
                if(flag%2==0) {
                    board[0][i][j]='B';
                    board[1][i][j]='W';
                }
                else {
                    board[0][i][j]='W';
                    board[1][i][j]='B';
                }
                flag++;
            }
            flag++;
        }



        //cal min
        int min=9999;
        for(int i=0;i<n-8+1;i++){
            for(int j=0;j<m-8+1;j++){
                min= Math.min(getDifferentCount(givenBoard,i,j),min);
            }
        }

        System.out.println(min);

    }
}