[백준/Java] 1018 체스판 다시 칠하기(2차원 배열, 비트 XOR 연산)

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

📝 풀이 2 : 2차원 배열에 문자 배열 저장 후 캐릭터 비교 (108ms)

• `(i + j)`가 짝수인지 여부에 따라 색상 비교

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

public class Main {
    // M×N 크기의 보드를 잘라서 8x8 크기의 체스판으로 만들 때, 다시 칠해야 하는 정사각형의 최소 개수 출력
    public static void main(String[] args) throws IOException {

        /* [1] 입력 */
        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()); // 열의 수

        char[][] board = new char[N][M]; // 보드 배열 생성
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray(); // 입력된 문자열을 문자 배열로 변환⭐
        }

        /* [2] 최솟값 찾기 */
        int minCount = Integer.MAX_VALUE; // 최솟값 초기화
        for (int row = 0; row <= N - 8; row++) {
            for (int col = 0; col <= M - 8; col++) {
                minCount = Math.min(minCount, getMinChanges(board, row, col)); // 함수 호출⭐
            }
        }
        System.out.println(minCount); // 결과 출력
    }

    // 8x8 영역에서 다시 칠해야 하는 최소 정사각형 개수 반환
    public static int getMinChanges(char[][] board, int startRow, int startCol) {

        int cntW = 0; // 다시 칠해야 하는 개수('W'로 시작하는 경우)
        int cntB = 0; // 다시 칠해야 하는 개수('B'로 시작하는 경우)

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                char current = board[startRow + i][startCol + j];
                /* [1] 체스판의 올바른 색상 이진수와 비교('W'로 시작하는 경우) */
                char chessColor = ((i + j) % 2 == 0) ? 'W' : 'B'; // 올바른 색상⭐
                if (current != chessColor) cntW++;
                /* [2] 체스판의 올바른 색상 이진수와 비교('B'로 시작하는 경우) */
                chessColor = chessColor == 'W' ? 'B' : 'W'; // 반대
                if (current != chessColor) cntB++;
            }
        }

        return Math.min(cntW, cntB); // 두 경우 중 더 적은 변경 횟수 반환⭐
    }
}

📝 풀이 1 : 1차원 배열에 문자열 저장 후 이진수 비트 XOR 연산 (160ms)

• 비트 연산자 이용
  • `^` (XOR, 배타적 논리합): 두 비트가 서로 다를 때 1
  • `~` (NOT, 비트 반전): 비트의 값 반전. 0은 1로, 1은 0으로 
  • `&` (AND, 논리곱): 두 비트가 모두 1일 때만 1
• `Integer.parseInt(String s, int radix)`, `Integer.bitCount(int i)` 메서드 ㅅ

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

public class Main {
    // M×N 크기의 보드를 잘라서 8x8 크기의 체스판으로 만들 때, 다시 칠해야 하는 정사각형의 최소 개수 출력
    public static void main(String[] args) throws IOException {

        /* [1] 입력 및 치환 */
        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()); // 열의 수

        String[] arr = new String[N]; // 1차원 배열 생성 (각 행 저장)
        for (int i = 0; i < N; i++) {
            String str = br.readLine(); // 한 행의 문자열 입력 (ex. WBWBWBWB)
            arr[i] = str.replaceAll("B", "1").replaceAll("W", "0"); // 'B'는 '1', 'W'는 '0'으로 치환하여 저장⭐
        }

        /* [2] 최솟값 찾기 */
        int cnt = 32; // 체스판을 다시 칠해야 하는 정사각형 개수 최댓값
        for (int row = 0; row <= N - 8; row++) {
            for (int col = 0; col <= M - 8; col++) { // 8x8 크기 체스판 선택 후, 다시 칠해야 하는 최소 정사각형 개수 찾기
                cnt = Math.min(cnt, getMinChanges(arr, row, col)); // 함수 호출⭐
            }
        }
        System.out.println(cnt);
    }

    // 8x8 영역에서 다시 칠해야 하는 최소 정사각형 개수 반환
    public static int getMinChanges(String[] arr, int startRow, int startCol) {

        int cntW = 0; // 다시 칠해야 하는 개수('W'로 시작하는 경우)
        int cntB = 0; // 다시 칠해야 하는 개수('B'로 시작하는 경우)

        for (int i = 0; i < 8; i++) {
            int current = Integer.parseInt(arr[i + startRow].substring(startCol, startCol + 8), 2);
            /* [1] 체스판의 올바른 색상 이진수와 비교('W'로 시작하는 경우) */
            int chess = Integer.parseInt((i % 2 == 0) ? "01010101" : "10101010", 2); // 올바른 색상 이진수⭐
            cntW += Integer.bitCount(chess ^ current); // 비트 XOR 연산 결과에서 1로 나타나는 부분이 다시 칠해야 하는 개수⭐
            /* [2] 체스판의 올바른 색상 이진수와 비교('B'로 시작하는 경우) */
            chess = ~chess & 0b11111111; // 비트를 반전하고, 8비트만 유지(이진수 상수를 사용하기 위해 0b 접두사 사용)
            cntB += Integer.bitCount(chess ^ current);
        }
        return Math.min(cntW, cntB); // 두 경우 중 더 적은 변경 횟수 반환⭐
    }
}