[백준/Java] 1018번 : 체스판 다시 칠하기

[문제]

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

[조건]

• 시간 제한 : 2초
• 메모리 제한 : 128MB

[입력]

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

[출력]

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

[문제 풀이]

• black, white라는 1차원 배열을 통해 한 줄의 모습을 만듦
• 각 줄마다 비교를 통해 해당 모습이 아닐경우 카운트해 가장 적은 경우를 출력

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int[][] board;
    static int[] black, white;
    static int N, M, min;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];
        min = Integer.MAX_VALUE;
        for (int r = 0; r < N; r++) {
            String text = br.readLine();
            for (int c = 0; c < M; c++) {
                board[r][c] = text.charAt(c) == 'B' ? -1 : 1;
            }
        }
        black = new int[] { -1, 1, -1, 1, -1, 1, -1, 1 };
        white = new int[] { 1, -1, 1, -1, 1, -1, 1, -1 };
        for (int r = 0; r < N - 7; r++) {
            for (int c = 0; c < M - 7; c++) {
                min = Math.min(min, check(r, c));
            }
        }
        System.out.println(min);

    }

    static int check(int r, int c) {
        int cntB=0, cntW=0;
        for (int i = r; i < r+8; i++) {
            for (int j = c; j < c+8; j++) {
                if((i-r)%2==0) {
                    if(board[i][j] != black[j-c]) {
                        cntB++;
                    }
                    if(board[i][j] != white[j-c]) {
                        cntW++;
                    }
                } else {
                    if(board[i][j] != white[j-c]) {
                        cntB++;
                    }
                    if(board[i][j] != black[j-c]) {
                        cntW++;
                    }
                }
            }
        }
        return Math.min(cntB, cntW);
    }
}

 

[소감]

• 체스판 모습을 확인하는 과정 고민

1. 행, 열 한 줄을 모두 더해 절댓값을 확인함 (black -1, white 1로 설정했기 때문에 0이 아닐 경우 체스판 모습이 아님)
   이는 black, white가 번갈아 나오고 있는지 확인할 수 없음
2. 배열의 현재 요소와 다음 요소가 같은지 체크
   이는 중복 체크될 우려가 있음
   또한 한 줄에 bbbwbwbb와 같이 연속되는 부분이 두 번 이상일 경우 곤란함

• 따라서 위와 같이 black과 white배열을 만들고 확인 진행함

 

출처 : 백준 https://www.acmicpc.net/problem/1018