1018번: 체스판 다시 칠하기

문제

M×N 크기의 보드가 주어집니다. 어떤 정사각형은 검은색('B')으로 칠해져 있고, 나머지는 흰색('W')으로 칠해져 있습니다. 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 합니다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 합니다. (즉, 인접한 두 칸은 다른 색상이어야 합니다.) 8×8 크기로 자를 수 있는 모든 위치에 대해 체스판 패턴으로 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 N과 M이 주어집니다. (8 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어집니다.
• 출력: 첫째 줄에 다시 칠해야 하는 정사각형 개수의 최솟값을 출력합니다.

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

풀이: 좌표의 홀짝성(Parity)을 활용한 완전 탐색

보드의 크기가 최대 50×50이므로, 가능한 모든 8×8 체스판의 시작점을 순회하며 칠해야 하는 개수를 세는 브루트포스 방식으로 해결할 수 있습니다.

• 시작점 순회: 8×8 크기를 확보해야 하므로, 시작점의 행 i는 0부터 N-8까지, 열 j는 0부터 M-8까지 순회합니다.
• 좌표의 홀짝성(Parity) 활용: 정상적인 체스판은 행 좌표와 열 좌표의 합이 짝수인 칸들은 모두 같은 색이고, 홀수인 칸들도 모두 같은 색입니다.
  • 탐색 중인 보드의 절대 좌표는 (y + i, x + j)입니다.
  • 이 두 좌표의 합인 (y + x + i + j)가 짝수일 때 'B'가 오고, 홀수일 때 'W'가 오는 패턴 하나를 기준으로 잡고, 이에 어긋나는 칸의 개수(cnt)를 셉니다.
• 반대 패턴 계산 (64 - cnt): 8×8 체스판은 총 64칸입니다. 만약 (0,0)이 'B'인 패턴으로 칠할 때 cnt개의 칸을 다시 칠해야 한다면, (0,0)이 'W'인 반대 패턴으로 칠할 때는 정확히 나머지 칸들인 64 - cnt개만 다시 칠하면 됩니다.
• 최솟값 갱신: 하나의 8×8 구간을 탐색할 때마다 Math.min(cnt, 64 - cnt)를 통해 두 체스판 패턴 중 더 적게 칠하는 값을 구하고, 이를 전체 최솟값 ans와 비교하여 갱신합니다.

코드

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

public class Main {
    static int n, m;
    static char[][] a;
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       n = Integer.parseInt(st.nextToken());
       m = Integer.parseInt(st.nextToken());
       a = new char[n][m];
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine().toCharArray();
       }

       // 8x8 크기로 자를 수 있는 모든 시작점 탐색
       for (int i = 0; i < n - 7; i++) {
          for (int j = 0; j < m - 7; j++) {
             checkBoard(i, j);
          }
       }

       bw.write(ans + "");

       bw.flush();
    }

    static void checkBoard(int y, int x) {
       int cnt = 0;
       
       // 시작점 (y, x)를 기준으로 8x8 영역 탐색
       for (int i = 0; i < 8; i++) {
          for (int j = 0; j < 8; j++) {
             // 좌표 합의 홀짝성으로 번갈아 나타나는 패턴 검사
             if ((i + j + y + x) % 2 == 0 && a[i + y][j + x] != 'B')
                cnt++;
             else if ((i + j + y + x) % 2 == 1 && a[i + y][j + x] != 'W')
                cnt++;
          }
       }

       // (현재 패턴 기준 칠하는 횟수) vs (반대 패턴 기준 칠하는 횟수) 중 최솟값으로 갱신
       ans = Math.min(ans, Math.min(cnt, 64 - cnt));
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force)