백준 1018 체스판 다시 칠하기

문제

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

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

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

입력

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

출력

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

 

package ch.ch.bong.baekjoon;

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

public class Algorithm1018 {
    static boolean[][] square;
    static int min = 64;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);
        square = new boolean[n][m];
        for(int i = 0; i < n; i ++){
            String str = br.readLine();
            for(int j = 0; j < m ; j++){
                square[i][j] = str.charAt(j) == 'W' ? true :  false;
            }
        }
        int row = n-7;
        int col = m-7;

        for(int i = 0; i < row; i ++){
            for(int j = 0 ; j < col ; j++){
                findCount(i,j);
            }
        }

        System.out.println(min);
    }

    private static void findCount(int row, int col) {
        int cnt = 0;
        boolean check = square[row][col];
        for(int i = row ; i < 8+row; i++){
            for(int j = col ; j < 8+col ; j++){
                if(square[i][j] != check){
                    cnt++;
                }
                check = !check;
            }
            check = !check;
        }
        min = Math.min(min, Math.min(cnt, 64 - cnt));
    }


}

 

풀이

일단 이 문제를 이해하는데 시간이 꽤 걸렸다.

처음에는 W와 B의 개수를 다 구해서 32개중에 부족한것만 찾으면 되는거 아니야  ? 라고 생각하고 문제를 풀었는데, 예제값이 달라서 다시보니 8줄만 만족하면되는구나, 라고 판단하고 다시 8줄 별로 비교하엿으나 문제가 발생했다. 가로도 8줄인걸 까먹고 있었던 것이다.

---

(혼자선 도저히 답을 모르겠어서 다른사람의 풀이를 이해하고 직접 짜보았다. )

---

 

그리하여 가로와 세로 둘다 8자리씩 비교하여야한다고 판단 하였고 B와 W를 boolean값으로 나타낸뒤

배열에 맞춰 사각형을 그려넣었다.

후에 반복문을 돌때  8x8만 맞으면 된다라고 생각할 수 있는데 그 이유는 만약 길이가 10인 사각형이라고 판단하면 시작점이 1 , 2, 3 일때 까지만 비교하면 된다. 

(이유는 4번째 시작점은 가로의길이가 7이기때문에 8을 만족하지 않는다)

그리하여 가로와 세로의 길이를 제공받은 것에 -7씩 하여 row, col로 나타내어주었다.

반복문을 도는 횟수를 row와 col로 찾았으니, findCount라는 메서드를 사용하여 최솟값을 찾는다.

 

findCount 에서는 row, col 즉, 판단해야될 가로줄의 개수 , 세로줄 개수를 넘겨받아서

boolean check를 시작점 즉 square[row][col]에 들어있는 W?인지 B?인지 판단하여 생성해준다.

그리고 이 check를 계속 반대로 반전시켜주면서 다음번에 다른색이 오는걸로 표현하고 , 줄이바뀔때도 다른색이 오게 만들어서 만약 색이 다르다면 cnt를 +하여 최솟값을 찾는 식으로 하였다.

* 여기서 최솟값은 어떻게 찾나요 ? 라고 생각할 수 있는데 간단하게도 findCount메서드는 void형태로 반환값이 없다. 

필드변수에 min을 통하여 최솟값을 자동적으로 비교하여 최종적으로 남아있는 min의 값이 최솟값이 나올수 있게 된다.

 

 

 

 

출처 - https://www.acmicpc.net/problem/1018