[BOJ/JAVA] 백준 25682 : 체스판 다시 칠하기 2 (자바)

문제 정보

  문제명   - 체스판 다시 칠하기 2
  난이도   - 골드 V
문제 번호 - 25682번

---

문제 링크

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

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

---

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

---

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
4 4 3 BBBB BBBB BBBW BBWB	2
8 8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
10 13 10 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB	30
9 23 9 BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBWWWWWWWW	40

---

알고리즘 분류

● 누적 합

---

소스코드

package Lv3_Gold;

import java.io.*;
import java.util.*;
/**
 * @author HanHoon
 * @category 누적 합
 * https://www.acmicpc.net/problem/25682
 */
public class BOJ_G5_25682_체스판_다시_칠하기_2 {
    static int N, M, K;
    static String[] board;

    // 해당 색깔로 시작하는 보드를 만들었을 때 다시 칠해야하는 정사각형 개수
    public static int makeBoard(char color){
        // 다시칠해야 하는 최솟값
        int cnt = Integer.MAX_VALUE;
        // 다시 칠해야하는 색깔의 누적 합
        int[][] dp = new int[N+1][M+1];
        // 누적합에 더할지 말지 판단
        int value = 0;

        for(int n = 0; n < N; n++){
            for(int m = 0; m < M; m++){
                // 짝수마다 color 색이어야 한다.
                if((n+m)%2 == 0)
                    value = board[n].charAt(m) != color? 1 : 0;
                // 홀수마다 color 반대색이어야 한다.
                else
                    value = board[n].charAt(m) == color? 1 : 0;

                // 누적합에 저장
                dp[n+1][m+1] = dp[n][m+1] + dp[n+1][m] - dp[n][m] + value;
            }
        }

        // 누적합을 통해 최솟값 판단
        for(int n = 1; n <= N-K+1; n++){
            for(int m = 1; m <= M-K+1; m++){
                cnt = Math.min(cnt,
                        // 행 누적값
                        dp[n+K-1][m+K-1] - dp[n+K-1][m-1]
                        // 열 누적값
                        - dp[n-1][m+K-1] + dp[n-1][m-1]);
            }
        }
        
        // 최솟값 출력
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder str = new StringBuilder();

        // MxN 크기의 보드
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        // KxK 크기의 체스판으로 만듦
        K = Integer.parseInt(st.nextToken());

        // B: 검은색, W: 흰색
        board = new String[N];
        for(int n = 0; n < N; n++)
            board[n] = br.readLine();

        // 어떤 색으로 시작했을 때 더 효율적인지?
        str.append(Math.min(makeBoard('B'), makeBoard('W')));

        // KxK 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값
        System.out.print(str);
        br.close();
    }
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---