체스판 다시 칠하기

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

---

제출코드

시간초과

package baekjoon;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int width;
    static int height;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String chessSize = br.readLine();

        for (int i = 0; i < chessSize.length(); i++) {
            char c = chessSize.charAt(i);
            int number = Character.getNumericValue(c);
            if (i == 0) {
                width = number;
            } else {
                height = number;
            }
        }

        Character[][] board = new Character[width][height];

        for (int i = 0; i < height; i++) {
            String input = br.readLine();
            for (int j = 0; j < input.length(); j++) {
                board[i][j] = input.charAt(j);
            }
        }

        Character[][] answerBoard = new Character[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if ((i + j) % 2 == 0) {
                    answerBoard[i][j] = 'W';
                } else {
                    answerBoard[i][j] = 'B';
                }
            }
        }
    }


    static int calc(Character[][] answerBoard, Character[][] board) {

    }
}

calc()를 통해 모든 경우의 수를 알아보는 방법을 떠올리는게 어려웠음.
그리고 문제이해를 잘못했음;;

예를 들어
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW 이 입력값이면

WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
와
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

중에 재색칠 개수가 더 적은 경우의 재색칠 갯수를 구하는 문제였다.

답안

package baekjoon;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int width;
    static int height;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ;
        String[] chessSize = br.readLine().split(" ");
        width = Integer.parseInt(chessSize[0]);
        height = Integer.parseInt(chessSize[1]);

        char[][] board = new char[width][height];

        for (int i = 0; i < width; i++) {
            String input = br.readLine();
            for (int j = 0; j < height; j++) {
                board[i][j] = input.charAt(j);
            }
        }

        int minRepaints = Integer.MAX_VALUE;
        for (int i = 0; i <= width - 8; i++) {
            for (int j = 0; j <= height - 8; j++) {
                minRepaints = Math.min(minRepaints, calc(board, i, j));
            }
        }
        System.out.println(minRepaints);
    }

    static int calc(char[][] board, int x, int y) {
        int endX = x + 8;
        int endY = y + 8;
        int repaints1 = 0; // 맨 왼쪽 위칸이 흰색
        int repaints2 = 0; // 맨 왼쪽 위칸이 검은색

        for (int i = x; i < endX; i++) {
            for (int j = y; j < endY; j++) {
                if ((i + j) % 2 == 0) {
                    if (board[i][j] != 'W') repaints1++;
                    if (board[i][j] != 'B') repaints2++;
                } else {
                    if (board[i][j] != 'B') repaints1++;
                    if (board[i][j] != 'W') repaints2++;
                }
            }
        }
    }
}

1. 우선 Integer.MAX_VALUE를 사용하여 minRepaints를 구할 수 있다.
   Math.min(Integer.MAX_VALUE, 변수); 를 사용하면 언제나 변수가 min일 것이므로 최소값을 초기화하는데 유용한 패턴이다. 또한 최소값을 찾기 위해 변수를 최대 가능한 값으로 초기화하는 것은 최소값 탐색 알고리즘에서 흔히 사용되는 패턴이다. 이는 최대값을 찾을 때 변수를 가능한 가장 작은 값(예: Integer.MIN_VALUE)으로 초기화하는 것과 대칭적이다.

2. calc는 재색칠 갯수를 구하는 함수다.
   x,y가 시작위치이고, 8을 각각 더한 것이 끝나는 위치다.
   이제 아까 위에서 언급한 두가지 체스판에 비교해야한다.

repaints1: 좌상단이 'W'인 체스 패턴에 맞추기 위해 재도색이 필요한 셀의 개수
repaints2: 좌상단이 'B'인 체스 패턴에 맞추기 위해 재도색이 필요한 셀의 개수

짝수 위치와 홀수 위치 구분:

(i + j) % 2 == 0: 체스판의 (i, j) 위치가 짝수인지 홀수인지를 판단한다. 짝수 위치는 체스판 패턴에서 첫 번째 색 (W 또는 B)가 있어야 하는 위치다.
(i + j) % 2 != 0: 체스판의 (i, j) 위치가 홀수임을 의미한다. 홀수 위치는 패턴에서 두 번째 색 (B 또는 W)가 있어야 하는 위치다.

짝수 위치 (i + j가 짝수일 때):
board[i][j] != 'W': 현재 셀이 'W'가 아니면 'W'로 시작하는 패턴에 맞추기 위해 재도색이 필요하므로 repaints1을 증가시킨다.
board[i][j] != 'B': 현재 셀이 'B'가 아니면 'B'로 시작하는 패턴에 맞추기 위해 재도색이 필요하므로 repaints2를 증가시킨다.

홀수 위치 (i + j가 홀수일 때):
board[i][j] != 'B': 현재 셀이 'B'가 아니면 'W'로 시작하는 패턴에 맞추기 위해 재도색이 필요하므로 repaints1을 증가시킨다.
board[i][j] != 'W': 현재 셀이 'W'가 아니면 'B'로 시작하는 패턴에 맞추기 위해 재도색이 필요하므로 repaints2를 증가시킨다.

---

전체적인 동작 순서는 다음과 같다:

1. 함수는 x와 y 인덱스에서 시작하여, 8x8 크기의 체스판 섹션을 확인한다. endX와 endY는 이 섹션의 끝 경계를 나타낸다.

2. 두 개의 카운터 repaints1과 repaints2는 각각 섹션이 흰색('W')으로 시작하는 패턴과 검은색('B')으로 시작하는 패턴을 따르기 위해 다시 칠해야 하는 칸의 수를 추적한다.

3. 이중 for 루프를 사용하여, 선택된 8x8 섹션의 모든 칸을 순회한다.

4. 각 칸에 대해, (i + j) % 2 == 0을 통해 칸의 위치가 짝수인지 홀수인지를 판별한다. 체스판에서 짝수 위치는 맨 왼쪽 위 칸과 동일한 색을 가져야 하고, 홀수 위치는 반대 색을 가져야 한다.

5. 칸의 색이 예상된 색과 일치하지 않는 경우, 해당 칸은 다시 칠해져야 한다. 이를 위해 repaints1 또는 repaints2가 증가한다.

6. 모든 칸을 확인한 후, repaints1과 repaints2 중 더 작은 값을 최소 다시 칠해야 하는 칸의 수로 결정한다. 즉, 이 단계에서 두 개의 경우의 수 중 어떤 것을 덜 재색칠 해야하는지 판별한다.

7. 만약 체스판 입력값이 이미 완벽한 패턴을 따르고 있다면, repaints1과 repaints2 모두 0이 될 것이다. 따라서 이 경우에는 다시 칠할 필요가 없다.

---

3. 두가지 경우의 수를 계산하면 calc가 끝난다.

        int minRepaints = Integer.MAX_VALUE;
        for (int i = 0; i <= width - 8; i++) {
            for (int j = 0; j <= height - 8; j++) {
                minRepaints = Math.min(minRepaints, calc(board, i, j));
            }
        }
        System.out.println(minRepaints);
    }

위 반복문이 끝날 때까지 과정을 반복한다...