[코딩 테스트] 체스판 다시 칠하기

문제 출처

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

 

체스판의 패턴에 맞게 색칠을 할건데, 가장 적은 횟수로 칠하는 수를 반환하면 되는 문제이다.

 

생각했던 고민은

1. 시간효율을 고민하였을 때, 어떤 식으로 8*8을 접근하는게 좋을까? 

2. 하나하나 다 패턴을 다 체크를 해야하는 건가?

 

1에 대한 해결법은 8*8로 모든 경우의 수를 보면 되는 것이고

2에 대한 해결법은 왼쪽 위에가 흰색으로 시작하는 경우 또는 검은색으로 시작하는 경우 한번만 구하면 된다.

 

아마도 이 문제의 핵심은 2에 대한 부분일 것 같다.

 

그래서 아래에서 어떤식으로 접근하였는지 그림으로 함께 보려고 한다.

 

1번에서 말한 8*8로 모든 경우의 수를 본다는 말은

다음과 같은 10 * 10 배열이 주어졌다고 가정해보자

 

접근은 이런 순서로 배열을 8*8로 하나씩 접근을 하면 된다.

 

그 다음 2번에서 말한 흰색으로 시작하는 패턴만 체크하면 된다 의 의미는

 

다음과 같은 2*2의 방식을 보며 설명해보겠다.

 

- 이런식으로 흰색 패턴으로 시작하는 경우를 가정하여 확인하면 1이 나오게 되고

- 검은색 패턴으로 시작하는 경우를 가정하여 확인하면 3이 나오게 된다

 

여기서 봐야할 것은 두개의 경우를 합치면 총 체스판의 갯수(4)가 나온다는 것이다.

- 이 점을 이용해서 두가지 경우의 수를 구하는게 아니라

- 흰색 패턴으로 시작하는 경우를 확인해서 count 변수로 센다음에

- Math.min(count, 64-count)를 하면 된다.

 

이 아이디어가 이 문제의 핵심 방법이라고 생각한다.

 

구현 코드

 

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

public class Main {
    private static char[][] board;
    private static final char[] white ={'W','B','W','B','W','B','W','B'};
    private static final char[] black ={'B','W','B','W','B','W','B','W'};

    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] aryLen = br.readLine().split(" ");

        //행, 열 저장
        int row =  Integer.parseInt(aryLen[0]);
        int col =  Integer.parseInt(aryLen[1]);

        //보드 배열을 담아둘 배열
        board = new char[row][col];
        for(int i = 0 ; i< row ; i++){
            board[i]=br.readLine().toCharArray();
        }
        int answer =64;

        for(int i = 0; i<= row- 8;i++){
            for(int j=0; j<= col-8;j++){
                int temp = countChess(i,j);

                if(answer > temp) answer=temp;
            }
        }



        System.out.println(answer);

    }

    private static int countChess(int row, int col){
        int count =0;
        for(int i=0;i<8;i++){
            for(int j = 0; j<8;j++){
                if(i%2==0){
                    if(board[row+i][col+j]==white[j]) count++;
                }else{
                    if(board[row+i][col+j]==black[j]) count++;
                }
            }
        }
        return Math.min(64-count,count);
    }
}