[백준]JAVA - 1018번: 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

풀이

이번 문제는 예제가 7개나 있는 고마운 문제이다. 매번 알고리즘 문제를 풀면서 반례를 찾는게 여간 쉬운 일이 아닌데 정말 고맙다.

 

8x8 이상의 크기를 입력하고 상하좌우 한 칸씩 색깔이 다른 8x8 크기의 체스판을 만드는데 색칠이 잘 못된 최소 개수를 구하는 문제이다. 만약 10x10 크기의 배열이 입력됐다고 하면 자를 수 있는 경우의 수는 얼마나 될까?

10x10 크기가 주어지면 경우의 수가 너무 많아서 다 보여주는 것도 힘들다. 경우의 수를 구하는 공식은 아래와 같다.

 

우선 맨 좌측 상단의 칸이 흰 색, 검은색으로 2가지이다. 두 번째로 가로와 세로 크기에 -7을 해줘서 구할 수 있는 경우의 수인데 이해하기 쉽게 풀어서 적어보겠다.

 

8x8 크기가 가질 수 있는 보드 개수: (8-7) x (8-7) = 1개

8x9 크기가 가질 수 있는 보드 개수: (8-7) x (9-7) = 2개

10x10 크기가 가질 수 있는 보드 개수: (10-7) x (10-7) = 9개

 

결론은 2 x (가로 길이 - 7) x (세로 길이 - 7) 이다.

map = new boolean[N][M];
for (int i=0; i<N; i++) {
    String str = br.readLine();
    for (int j=0; j<M; j++) {
        if (str.charAt(j) == 'W') map[i][j] = true;
        else map[i][j] = false;
    }
}

처음에 char형으로 map 배열을 생성했다가 잘 못된 색깔을 체크할 때 if~else문을 추가해서 작성해야하는 불편함과 가독성을 높이기 위해서 boolean형으로 만들었다. 흰 색은 true, 검은색은 false로 설정해주고 색깔을 체크할 때 한 칸씩 넘어갈 때마다 WB = !WB로 색상을 변경해주었다.

 

<최종코드>

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

public class Main {
    static boolean[][] map;
    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(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
		
        map = new boolean[N][M];
        for (int i=0; i<N; i++) {
            String str = br.readLine();
            for (int j=0; j<M; j++) {
                if (str.charAt(j) == 'W') map[i][j] = true;
                else map[i][j] = false;
            }
        }
		
        for (int i=0; i<N-7; i++) {
            for (int j=0; j<M-7; j++) {
                check(i,j);
            }
        }
		
        System.out.println(min);
    }
	
    public static void check(int x, int y) {
        int cnt = 0;
		
        boolean WB = map[x][y]; 
        for (int i=x; i<x+8; i++) {
            for (int j=y; j<y+8; j++) {
                if (map[i][j] != WB) cnt++;
				
                WB = !WB; // 이전 칸의 색깔과 달라야함.
            }
            WB = !WB; // 이전 행의 마지막 칸과 색깔이 달라야함.
        }
        cnt = Math.min(cnt, 64-cnt); // 정삭적인 색깔을 변경하는 게 더 적을 수 있기 때문.
        min = Math.min(min, cnt);
    }
}