[백준] 1018번_체스판 다시 칠하기(Java)

문제 풀이

백준의 1018번 문제입니다. 문제 출처

(1) 문제 파악

가지고 있는 보드를 잘라 체스판을 만드는 문제입니다.

(2) 문제 풀이 방법 생각하기

체스판의 크기는 8 * 8로 고정되어 있으니 보드가 주어지면 만들 수 있는 체스판의 개수가 나옵니다.

색칠할 칸의 최소 개수를 구하는 문제이므로, 가능한 보드를 모두 잘라 확인해보고 최소값을 구하는 방식으로 풀 수 있을 것입니다.

(3) 시간 복잡도 확인

시간 제한은 2초 입니다. 즉, 대략 2억번 연산 안에 문제를 해결해야 합니다.

체스판을 모두 확인하며 뒤집어야 하는 판 개수를 찾는 연산은 8 * 8 = 64번 수행됩니다.

또한 N과 M의 값은 8보다 크고 50보다 작은 자연수이므로 최대 N과 M은 49입니다. \(8<N, M<50\)

최대 (49 - 8 + 1) * (49 - 8 + 1) = 1,764 개의 체스판을 만들어 뒤집어야 하는 판의 개수를 찾을 수 있습니다.

즉, 최대 (64 * 1764) 번의 연산이 수행되므로 가능합니다.

(4) 구현

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

public class Main {
    static boolean[][] board; // W는 true, B는 false
    static int min = 64; 
    
    public static void main(String[] args) throws IOException {
        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());
        board = new boolean[N][M];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                if(str.charAt(j) == 'W') board[i][j] = true;
                else board[i][j] = false;
            }
        }
        
        for(int i=0; i<N-7; i++) {
            for(int j=0; j<M-7; j++) {
                find(i, j);
            }
        }
        
        System.out.println(min);
        br.close();
    }
    
    private static void find(int start_x, int start_y) {
        int end_x = start_x+8;
        int end_y = start_y+8;
        int count = 0;
        
        boolean target = board[start_x][start_y];
        
        for(int i=start_x; i<end_x; i++) {
            for(int j=start_y; j<end_y; j++) {
                if(board[i][j] != target) count++;
                target = (!target);
            }
            target = (!target);
        }
       
        count = Math.min(count, 64-count); // board[start_x][start_y]로 시작하는 경우 vs 반대 색상으로 시작하는 경우
        min = Math.min(min, count);
    }
}