[JAVA] 체스판 다시 칠하기

NoHae·2025년 3월 19일

백준

목록 보기

22/106

문제 출처

단계별로 풀어보기 > 브루트 포스 > 체스판 다시 칠하기
https://www.acmicpc.net/problem/1018

문제 설명

MxN 크기의 보드(단위 정사각형으로 나뉘어짐)가 있을 때, 어떤 정사각형은 검은색, 나머지는 흰색으로 칠해져 있다.
이 보드를 임의의 구역을 8x8로 잘라서 체스판으로 만들었을 때,
체스판은 검은색과 흰색 혹은 흰색 검은색 순서를 지키면서 칠해져있어야한다.
이 때, 색을 다시 칠해야하는 정사각형의 최소 개수를 구하여라

접근 방법

MxN의 보드를 8x8 체스판으로 만들기 위해서는 해당 보드의 시작점을 구하고, 그 시작점으로 부터 x,y 각각 8칸씩 잘라내어야 한다.
이를 통해 처음 시작하는 좌표를 startX, startY라고 설정하고, 각 시작 좌표 마다 하얀색 블록 카운트 countW, 검은색 블록 카운트 countB를 초기화한다.

이 후, 각 보드의 위치에 따라서 시작점과 동일해야하는 블럭, 시작점과 달라야하는 블럭의 경우를 세어 이 중 최솟값을 구한다.

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

public class 체스판_다시_칠하기 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        String[][] board = new String[N][M];

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

        int minPaint = Integer.MAX_VALUE;

        for (int startX = 0; startX <= N - 8; startX++) {
            for (int startY = 0; startY <= M - 8; startY++) {
                // 두 가지 경우의 count (W 시작 / B 시작)
                int countW = 0;
                int countB = 0;

                for (int i = 0; i < 8; i++) {
                    for (int j = 0; j < 8; j++) {
                        // 현재 칸의 색
                        String current = board[startX + i][startY + j];
                        // (i+j) 합이 짝수인 칸과 홀수인 칸의 색이 교차해야 함
                        if ((i + j) % 2 == 0) { // 해당 식에 대해서는 그림 그려서 파악
                            if (!current.equals("W")) countW++;
                            if (!current.equals("B")) countB++;
                        } else {
                            if (!current.equals("B")) countW++;
                            if (!current.equals("W")) countB++;
                        }
                    }
                }

                // 더 작은 값으로 갱신
                minPaint = Math.min(minPaint, Math.min(countW, countB));
            }
        }

        System.out.println(minPaint);
    }
}

Review

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

public class 체스판_다시_칠하기_review {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        String[][] board = new String[N][M];

        // 보드 입력 받기
        for(int i = 0; i<N; i++){
            String line = br.readLine();
            for(int j = 0; j<M; j++){
                board[i][j] = String.valueOf(line.charAt(j));
            }
        }

        int min = Integer.MAX_VALUE;

        for(int startX = 0; startX<=N-8; startX++){
            for(int startY = 0; startY<=M-8; startY++){
                int countW = 0;
                int countB = 0;
                for(int k = startX; k<startX+8; k++){
                    for(int l = startY; l<startY+8; l++){
                        String current = board[k][l];

                        if((k+l)%2 == 0){
                            if(!current.equals("W")) countW++;
                            if(!current.equals("B")) countB++;
                        } else {
                            if(!current.equals("W")) countB++;
                            if(!current.equals("B")) countW++;
                        }
                    }
                }

                min = Math.min(min, Math.min(countW, countB));
            }
        }

        bw.write(String.valueOf(min));
        bw.flush();
        bw.close();
        br.close();
    }

}