[백준] 25682 체스판 다시 칠하기2 - Java

 

 

 

문제 출저

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

25682번: 체스판 다시 칠하기 2

 

 

 

문제 풀이

검은색과 흰 색으로 칠해진 n, m 크기의 판이 주어집니다. 변인 k인 정사각형으로 자릅니다. 이 정사각형을 올바른 체스판으로 만들기 위해서 색칠을 칠해야 할 때 최소한의 칠하는 횟수를 구해야 합니다.

 

누적합으로 풀었습니다. 

체스판은 2가지 경우가 있습니다. 왼쪽 위가 검은색이거나 흰색일 경우 입니다. 2가지 상황에 맞는 누적합 배열을 구해서 모든 경우의 수를 비교하여 최소값을 구했습니다.

 

 

소스 코드

package baekjoon.backjoon10.day2131.day30;

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

/*
체스판 다시 칠하기2
https://www.acmicpc.net/problem/25682

왼쪽 위가 흰색일 때, 검은색 일 때 각각의 prefix를 구한다.
 */
public class B25682 {

  static int n,m,k;
  static int[][] board;

  static int[][] blackBoard;
  static int[][] whiteBoard;

  static int[][] prefixBlackBoard;
  static int[][] prefixWhiteBoard;

  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());
    k = Integer.parseInt(st.nextToken());

    board = new int[n][m];

    for(int i = 0; i < n; i++) {
      String s = br.readLine();
      for(int j = 0; j < m; j++) {
        if(s.charAt(j) == 'B') {
          board[i][j] = 1;
        }
        else {
          board[i][j] = 0;
        }
      }
    }

    blackBoard = new int[n+1][m+1];
    whiteBoard = new int[n+1][m+1];

    for(int i = 1; i < n+1; i++) {
      for(int j = 1; j < m+1; j++) {

        if( (i-1+j-1) % 2 == 0) {
          if(board[i-1][j-1] == 0) {
            blackBoard[i][j] = 1;
          }
          else if(board[i-1][j-1] == 1) {
            whiteBoard[i][j] = 1;
          }
        }

        if( (i-1+j-1)%2 == 1) {
          if(board[i-1][j-1] == 1) {
            blackBoard[i][j] = 1;
          }
          else if(board[i-1][j-1] == 0) {
            whiteBoard[i][j] = 1;
          }
        }
      }
    }


    prefixBlackBoard = new int[n+1][m+1];
    prefixWhiteBoard = new int[n+1][m+1];


    for(int i = 1; i < n+1; i++) {
      for(int j = 1; j < m+1; j++) {
       prefixBlackBoard[i][j] = blackBoard[i][j] + prefixBlackBoard[i-1][j] + prefixBlackBoard[i][j-1] - prefixBlackBoard[i-1][j-1];
       prefixWhiteBoard[i][j] = whiteBoard[i][j] + prefixWhiteBoard[i-1][j] + prefixWhiteBoard[i][j-1] - prefixWhiteBoard[i-1][j-1];
      }
    }

    int answer = m*n;

    for(int i = k; i < n+1; i++) {
      for(int j = k; j < m+1; j++) {
        int blackResult = prefixBlackBoard[i][j] - prefixBlackBoard[i-k][j] - prefixBlackBoard[i][j-k] + prefixBlackBoard[i-k][j-k];
        int whiteResult = prefixWhiteBoard[i][j] - prefixWhiteBoard[i-k][j] - prefixWhiteBoard[i][j-k] + prefixWhiteBoard[i-k][j-k];

        answer = Math.min(answer, blackResult);
        answer = Math.min(answer, whiteResult);

      }
    }

    System.out.println(answer);

  }

  public static void printBoard() {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        System.out.print(board[i][j] + " ");
      }
      System.out.println();
    }
    System.out.println();
  }

  public static void printBlackBoard() {
    for(int i = 1; i < n+1; i++) {
      for(int j = 1; j < n+1; j++) {
        System.out.print(blackBoard[i][j] + " ");
      }
      System.out.println();
    }
    System.out.println();
  }

  public static void printWhiteBoard() {
    for(int i = 1; i < n+1; i++) {
      for(int j = 1; j < n+1; j++) {
        System.out.print(whiteBoard[i][j] + " ");
      }
      System.out.println();
    }
    System.out.println();
  }

}