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

이번에는 BOJ의 1018번 문제 "체스판 다시 칠하기"를 풀어보도록 하자

먼저 문제설명을 해보자면, 지민친구가 8 * 8 크기의 체스판을 만들려고 하는데, 주어진 N * M 크기의 보드가 검정 / 흰색 패턴이 번갈아가며 칠해져 있지 않아 따로 칠해줘야 된다. 이 때, 8 * 8크기로 보드를 자른뒤에 다시 칠해야하는 정사각형의 개수의 최솟값을 구하는 프로그램을 구해야 되는 문제이다. 입력으로는 처음에 N과 M이 주어지고, 둘째 줄부터 N개의 줄만큼 체스판의 색상태가 주어진다. (B는 검정색이고, W는 희색이다.) 그리고, 출력으로는 지민이가 다시 칠해야하는 정사각형 개수의 최솟값을 출력하면 되는 문제이다.

이 문제는, 목표지점을 사진을 찍듯이 찍어서, 기존의 체스판과 얼마나 다른지 비교하면 되는 문제이다. 그러기 위해선, 기존의 체스판에 대한 정보가 필요하다.

static String[] chesspan = {"WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", 
                        "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW"};

 그리고, 여기에서 주의해야 될 점은 기존의 체스판을 거꾸로 뒤집어도 된다는 점인데,

static String[] chesspan = {"BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB" 
                        "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB"};

이렇게도 비교를 해줘야된다는 것이다. 매번 이렇게 비교해주기 싫다면, 전체 체스판의 정사각형 개수가 64개인 것을 이용해서, 아래와 같이 cnt(카운트)해준 것이 32번 보다 클 때, 64에서 cnt를 빼주게 되면, 체스판을 거꾸로 해줬을 때, 다시 칠해야 되는 가장 작은 값을 구할 수가 있다.

if(cnt >= 32) cnt = 64 - cnt;

성공한 코드는 아래와 같다.

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

public class sample {
    static String[] chesspan = {"WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", 
                        "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW"};
    public static void main(String[] args) throws Exception {
        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[] input = new String[N];
        for(int i = 0; i < N; i++){
            input[i] = br.readLine();
        }

        int ans = Integer.MAX_VALUE;
        for(int i = 0; i <= N - 8; i++){
            for(int j = 0; j <= M - 8; j++){
                int cnt = 0;
                for(int k = 0; k < 8; k++){
                    //계산을 진행 할 위치의 값들을 임시로 받아옴
                    String temp = input[i + k].substring(j, j + 8);
                    for(int l = 0; l < 8; l++){
                        if(temp.charAt(l) == chesspan[k].charAt(l)){
                            cnt++;
                        }
                    }
                }
                if(cnt >= 32) cnt = 64 - cnt;
                ans = Math.min(ans, cnt);
            }
        }
        bw.write(ans + "\n");
        
        bw.flush();
        br.close();
        bw.close();
    }
}

 

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

1018번: 체스판 다시 칠하기