[백준] 1018번 체스판 다시 칠하기(JAVA)

문제

- 입력받은 MxN 보드판에서 8x8 크기만큼 떼어내어 체스판처럼 칠하는 문제

- 각 칸이 검은색, 흰색으로 번갈아가면서 칠해져 있어야 함

- 8x8 크기는 아무데서나 골라서 사용

- 다시 칠해야 하는 정사각형(1x1)의 최소 개수 구하기

 

해결방법

처음에는 8x8 체스판을 가져왔을 때, (0, 0) 위치의 색을 가져와서 번갈아가면서 색을 비교하는 코드를 작성하였다.

하지만, testcase 4번에서 마지막에 W로 색칠되어 있었기 때문에 한 번 덜 색칠하고도 체스판을 다시 칠할 수 있었다.

 

따라서, (0, 0) 위치의 색을 가져와서 색을 비교하는 방식으로 진행한 것이 아니라 B으로 시작하는 체스판, W로 시작하는 체스판을 이용하여 비교할 수 있도록 하였다.

 

코드

- Testcase 4번 error 코드

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

class Main{
    static boolean[][] chess;
    static int result = Integer.MAX_VALUE;
    static int N, M;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        chess = new boolean[N][M];  // W : true, B : false

        // 보드판 입력 받기
        for(int i = 0; i<N; i++){
            String s = br.readLine();
            for(int j = 0; j<M; j++){
                if(s.charAt(j) == 'W'){
                    chess[i][j] = true;
                }else{
                    chess[i][j] = false;
                }
            }
        }

        checkchess();

        System.out.println(result);

        br.close();
    }

    // 8x8 크기로 입력받은 보드판 탐색
    static void checkchess(){
        for(int i = 0; i<=N-8; i++){
            for(int j = 0; j<=M-8; j++){
                comparechess(i, j);
            }
        }
    }

    // 8x8 크기의 체스판 내부 탐색
    static void comparechess(int r, int c){
        boolean condition = chess[r][c];	// 체스판 전 칸의 정보 저장
        boolean first = chess[r][c];		// 체스판 첫번째 칸에는 윗 줄이랑 다른색이여야 하므로 첫번째 정보 저장
        int count = 0;				// 다시 칠한 횟수

        for(int i = r; i<r+8; i++){
            if(i>r && first == chess[i][c]){	// 두번째 줄부터 첫번째 칸 비교
                count++;			// 다른색을 가져야하는데 같은색을 가지고 있으면 다시 칠하기
                first = !chess[i][c];
                condition = !chess[i][c];
            }else {				// 다른색을 가지고 있으면 정보 update
                first = chess[i][c];
                condition = chess[i][c];
            }
            for(int j = c+1; j<c+8; j++){	// 한 칸씩 탐색
                if(!condition == chess[i][j]){
                    condition = chess[i][j];
                }else{				// 다음칸이 이전칸이랑 색이 같으면 다시 칠해야 함
                    count++;
                    condition = !chess[i][j];
                }
            }
        }

        if(count<result) result = count;	// 다시 칠한 횟수가 최소가 될 수 있도록 update
    }
}

- 통과 코드

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

class Main{
    static boolean[][] chess;
    static int result = Integer.MAX_VALUE;
    static int N, M;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        chess = new boolean[N][M];  // W : true, B : false

	// 보드판 입력 받기
        for(int i = 0; i<N; i++){
            String s = br.readLine();
            for(int j = 0; j<M; j++){
                if(s.charAt(j) == 'W'){
                    chess[i][j] = true;
                }else{
                    chess[i][j] = false;
                }
            }
        }

        checkchess();

        System.out.println(result);

        br.close();
    }

    // 8x8 크기로 입력받은 보드판 탐색
    static void checkchess(){
        for(int i = 0; i<=N-8; i++){
            for(int j = 0; j<=M-8; j++){
                W_comparechess(i, j);
                B_comparechess(i, j);
            }
        }
    }

    // 8x8 크기의 체스판 내부 탐색('W'색부터 탐색)
    static void W_comparechess(int r, int c){
        boolean condition = true;	// 체스판 전 칸의 정보 저장
        boolean first = true;		// 체스판 첫번째 칸에는 윗 줄이랑 다른색이여야 하므로 첫번째 정보 저장
        int count = 0;			// 다시 칠한 횟수

        if(first != chess[r][c]) count++;	// 첫번째 칸이 'W'색이 아니라면 횟수 증가

        for(int i = r; i<r+8; i++){
            if(i>r && first == chess[i][c]){	// 두번째 줄부터 첫번째 칸 비교
                count++;			// 다른색을 가져야하는데 같은색을 가지고 있으면 다시 칠하기
                first = !chess[i][c];
                condition = !chess[i][c];
            }else if(i>r && first != chess[i][c]) {	 // 다른색을 가지고 있으면 정보 update
                first = chess[i][c];
                condition = chess[i][c];
            }
            for(int j = c+1; j<c+8; j++){	// 한 칸씩 탐색
                if(!condition == chess[i][j]){
                    condition = chess[i][j];
                }else{				// 다음칸이 이전칸이랑 색이 같으면 다시 칠해야 함
                    count++;
                    condition = !chess[i][j];
                }
            }
        }

        if(count<result) result = count;	// 다시 칠한 횟수가 최소가 될 수 있도록 update
    }

    // 8x8 크기의 체스판 내부 탐색('B'색부터 탐색)
    static void B_comparechess(int r, int c){
        boolean condition = false;	// 체스판 전 칸의 정보 저장
        boolean first = false;		// 체스판 첫번째 칸에는 윗 줄이랑 다른색이여야 하므로 첫번째 정보 저장
        int count = 0;			// 다시 칠한 횟수

        if(first != chess[r][c]) count++;	// 첫번째 칸이 'B'색이 아니라면 횟수 증가

        for(int i = r; i<r+8; i++){
            if(i>r && first == chess[i][c]){	// 두번째 줄부터 첫번째 칸 비교
                count++;			// 다른색을 가져야하는데 같은색을 가지고 있으면 다시 칠하기
                first = !chess[i][c];
                condition = !chess[i][c];
            }else if(i>r && first != chess[i][c]) {	 // 다른색을 가지고 있으면 정보 update
                first = chess[i][c];
                condition = chess[i][c];
            }
            for(int j = c+1; j<c+8; j++){	// 한 칸씩 탐색
                if(!condition == chess[i][j]){
                    condition = chess[i][j];
                }else{				// 다음칸이 이전칸이랑 색이 같으면 다시 칠해야 함
                    count++;
                    condition = !chess[i][j];
                }
            }
        }

        if(count<result) result = count;	// 다시 칠한 횟수가 최소가 될 수 있도록 update
    }
}