[백준 / Java] 1018번: 체스판 다시 칠하기 (브루트포스 알고리즘)

 

 

오늘의 문제는 백준 1018번 '체스판 다시 칠하기'다.

 

 

 

 

접근 방법

1. M*N 크기의 보드를 8*8 크기의 체스판으로 잘라낸 후 다시 칠해야 하는 정사각형의 최소 개수를 구한다.
2. 체스판은 검은색과 흰색이 번갈아서 칠해쳐 있어야 한다.

 

알고리즘 진행 순서

1. 입력된 값을 배열에 넣는다.
2. 8 x 8 크기의 체스판을 자를 수 있는 구간 안에서 다시 칠해야 하는 값(count)의 최소값을 구한다.
3. count는 8 x 8  체스판 안에서 시작 색과 같을 경우와 아닌 경우를 구분하여 각각 다시 칠해야 하는 개수를 ++하고 그 중 최솟값을 반환한다.
4. 최솟값을 출력한다.

 

구현 코드

package Boj;
// 체스판 다시 칠하기

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

public class Boj1018 {
    static int N, M = 0;
    static char[][] arr;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new char[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        for (int i = 0; i < N - 7; i++) {  // 체스판을 자를 수 있는 시작점
            for (int j = 0; j < M - 7; j++) {
                min = Math.min(min, getCount(i, j));
            }
        }
        System.out.println(min);
    }

    static int getCount(int x, int y) {
        int countX = 0;
        int countY = 0;

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                char cur = arr[x + i][y + j];

                if ((i + j) % 2 == 0) {
                    if (cur != 'W') countX++;
                    if (cur != 'B') countY++;
                } else {
                    if (cur != 'B') countX++;
                    if (cur != 'W') countY++;
                }
            }
        }

        return Math.min(countX, countY);
    }
}

회고

1. 문제 아이디어를 쉽게 생각해내지 못해서 검색을 시도했다.
2. 체스판을 자를 수 있는 시작점 (N-7, M-7)을 쉽게 이해하지 못했다.
3. 연습을 더 많이 하자!!!