1018번 - 체스판 다시 칠하기

uchan·2023년 11월 3일

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

문제(요약)

이차원 배열에서 8 x 8 크기를 가진 정사각형을 잡는다. 그리고 해당 정사각형에서 흰색과 검은색이 번갈아 나오도록 정사각형 내부의 원소 값을 수정한다. 이차원 배열에서 쪼갤 수 있는 8 x 8 정사각형 중 가장 적은 횟수로 수정할 수 있는 정사각형을 찾고 수정한 횟수를 출력한다.

풀이

이차원 배열에서 쪼갤 수 있는 8 x 8 정사각형을 모두 찾는다.
그리고 해당 정사각형에서 가장 왼쪽 상단에 있는 원소 값을 가정하고 조건(흰색과 검은색이 번갈아 나오도록)을 만족하도록 정사각형을 수정한다.
- 가장 왼쪽 상단에 있는 원소가 흰색일 경우
- 가장 왼쪽 상단에 있는 원소가 검은색일 경우

detail

이차원 배열의 원소 값은 'W', 'B' 둘 중 하나만 가질 수 있으므로 boolean 으로 받아준다.
N x M 크기를 가진 이차원 배열에서 쪼갤 수 있는 8 x 8 정사각형은 다음과 같다
- 정사각형의 가장 왼쪽 상단에 있는 원소의 좌표가 (y, x) 일 때
  - 가장 오른쪽 하단에 있는 원소의 좌표는 (y + 7, x + 7) 이다.
  - (y + 7, x + 7) 은 (N, M) 을 넘어갈 순 없다.

Code

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

public class Main {
    public static boolean[][] arr;
    public static int min = 64;

    public static void main(String[] args) throws IOException {
//        System.setIn(new FileInputStream("input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int max_y = Integer.parseInt(st.nextToken());
        int max_x = Integer.parseInt(st.nextToken());

        boolean[][] board = new boolean[max_y][max_x];

        for (int y = 0; y < max_y; y++) {
            String str = br.readLine();
            for (int x = 0; x < max_x; x++) {
                if (str.charAt(x) == 'W') {
                    board[y][x] = true;
                } else {
                    board[y][x] = false;
                }

            }
        }


        int max_start_y = max_y - 7;
        int max_start_x = max_x - 7;
        int min = 99999999;

        for (int y = 0; y < max_start_y; y++) {
            for (int x = 0; x < max_start_x; x++) {
                min = Math.min(min, calculate(board, false, y, x));
                min = Math.min(min, calculate(board, true, y, x));
            }
        }
        System.out.println(min);
    }

    public static int calculate(boolean[][] board, boolean current, int start_y, int start_x) {
        int count = 0;
        int end_y = start_y + 8;
        int end_x = start_x + 8;
        for (int y = start_y; y < end_y; y++) {
            for (int x = start_x; x < end_x; x++) {
                if (current == board[y][x]) {
                    count += 1;
                }
                current = (!current);
            }
            current = (!current);
        }
        return count;
    }
}