1. Problem 📃

[ 체스판 다시 칠하기 ]

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

[ 문제 ]

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

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

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

2. Input 📇

[ 입력 ]

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

3. Output 📠

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

예제 입력	예제 출력
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB	12
8 8 BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB	0
9 23 BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBW	23
10 10 BBBBBBBBBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBBBBBBBBB	0
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWWWB BWBWBWBW	2
11 12 BWWBWWBWWBWW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBWWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW	15

5. Solution 🔑

1. 처음 판의 길이를 받아줄 변수(N과 M)를 선언하여 값을 받아 배열로 표현 할 배열 변수(board)의 길이를 N행 M열 만큼 선언하여준다. 이때 선언은 static으로, 전역 변수로 선언하여 판을 체크해줄 메서드를 만들 때 사용하기 쉽도록 해주었다.
   
   
2. 가장 적게 바꿔야하는 개수를 세어줄 변수(min)를 선언하여 정수형의 최댓값으로 초기화해주고 메서드에서 바꾼 개수를 받을 result값을 선언하여 0으로 초기화한다.
   
   
3. 판을 체크할 메서드를 만들어보자. 매개변수는 보드의 몇 번째 칸부터 확인 할 것인지에 대한 인덱스값을 두 개(행, 열) 받아주고 리턴해줄 고친 값을 담아줄 변수(fix)를 선언하고 0으로 초기화한다.
   
   
4. 확인할 색을 담을 변수(color)를 선언하는데 초기화 값은 0행 0열(0, 0)부분을 넣어준다.
   보드를 한 칸씩 확인하면서 color변수를 B,W를 한번씩 번갈아가면서 바꿔주면서 보드를 한 칸씩 확인하며 값이 맞는지 확인한다. 이때 확인 할 칸의 수는 내가 받은 인덱스부터 +8값 까지 확인한다. 만약 나와야 할 color값과 board[i][j] 해당 칸의 색이 다르다면 고쳐야할 값(fix)를 증가(++)시켜준다.
   만약 color값이 초반에 W라면 위에 첫 칸이 B일 때와 반대로 코드를 작성하여준다.
   
   
5. 한 줄에 8개이므로 처음 나온 color값과 다음 줄 첫 번째 칸은 다른 색이 나오므로 한 행이 끝나면 color를 반대로 바꾸어 그 다음 줄을 확인한다.
   
   
6. 최종적인 fix값을 받는데, 만약 BWBWBWBW... 이 아닌 WBWBWBWB...로 했을 때 더 적은 fix값이 나오는 경우가 있을텐데 이를 확인하기 위해 반대되는 상황을 코드로 작성해야하나 했는데 다른 사람의 풀이를 보고 이를 확인하는 방법은 전체칸 ( 8 x 8 = 64 )에서 한 상황의 정정값을 빼어서 둘 중 작은 값 [ Math.min(fix, 64-fix) ]을 fix값에 담아주는 방법이 있는 것을 다른 사람들의 풀이를 보고 깨달았다. 이를 이용하여 작은 값을 반환한다.
   
   
7. 함수를 호출하여 반환된 값을 변수 result에 받고 가장 작은 값을 표시할 min과 비교하여 더 작다면 min을 result값으로 바꿔준다.
   그리고 계속해서 다음 칸을 확인하는데 또 이때 확인 할 값은 나 자신으로부터 8칸을 확인할 것이므로 매개변수로 넘겨줄 첫 인덱스 위치는 N-7과 M-7이다.
   
   
8. 다 확인하면 가장 작은 min값이 담겨있을텐데 min값을 출력한다.

6. Code 💻

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

public class Main {
	
	static int N;
	static int M;
	
	static char[][] board;
	
	public static int check(int x, int y) {
		int X = x + 8;
		int Y = y + 8;
		
		int fix = 0;
		
		char color = board[x][y];
		
		for(int i=x; i<X; i++) {
			if(board[x][y] == 'B') {		
				for(int j=y; j<Y; j++) {
					if(board[i][j] != color) {
						fix++;
					}
					if(color == 'B') {
						color = 'W';
					}
					else if(color == 'W') {
						color = 'B';
					}
				}
			}
			if(board[x][y] == 'W') {		
				for(int j=y; j<Y; j++) {
					if(board[i][j] != color) {
						fix++;
					}
					if(color == 'B') {
						color = 'W';
					}
					else if(color == 'W') {
						color = 'B';
					}
				}
			}
			if(color == 'B') {
				color = 'W';
			}
			else if(color == 'W') {
				color = 'B';
			}
		}
		fix = Math.min(fix, 64-fix);
		
		return fix;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		board = new char[N][M];
		
		int min = Integer.MAX_VALUE;
		int result = 0;
		
		for(int i=0; i<N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		
		for(int i=0; i<N-7; i++) {
			for(int j=0; j<M-7; j++) {
				result = check(i, j);
				if(result < min) {
					min = result;	
				}
			}
		}
		System.out.println(min);
	}

}

7. Growth 🍄

반대되는 상황 = [ 전체 상황 - 일어난 상황 ]으로 나타낼 수 있는 것을 생각할 수 있게 해주었던 문제였다.