[백준] 1018번 : 체스판 다시 칠하기 [자바 / JAVA]

---

모든 경우를 고려하는 브루트포스 알고리즘 범주의 문제이다.

N * M 크기의 보드가 주어지면, 최소 횟수로 칠할 수 있는 8 X 8 크기의 조각을 찾아내는 것이 목적이다.

 

N * M 보드에서 8 X 8 크기의 보드를 추출하는 경우의 수는 (N - 7) * (M - 7) 이다.

 

추출한 8X8 보드의 맨왼쪽 상단의 블럭 색의 경우의 수는 'W', 'B' 인 경우 2가지 이다.

 

따라서 우리가 고려해야할 경우의 수는 2 * (N - 7) * (M - 7) 이다.

 

보드 조각의 색은 'W'와 'B' 두 가지뿐 이므로, boolean 배열을 사용하여 표시한다. ('W' : true, 'B' : false)

 

 

---

보드의 색상을 저장할 boolean 배열과 구할 최솟값을 선언한다.

public static boolean[][] board;
public static int min = 64;

---

배열의 크기를 입력받는다.

boolean형의 2차원 배열 board에 보드의 색상을 입력받는다. ('W' : true, 'B' : false)

        // 공백으로 입력 받기 위함.
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 가로 길이
        int M = Integer.parseInt(st.nextToken()); // 세로 길이

        board = new boolean[N][M];

        // board 입력 받기
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken().toString();

            for(int j=0; j<M; j++){
                if(str.charAt(j) == 'W'){
                    board[i][j] = true;
                }
                else {
                    board[i][j] = false;
                }
            }
        }

---

8X8 크기의 보드의 색변환 최솟값을 찾는 메소드 find를 생성한다.

    // 주어진 8X8 보드에서 바꿔야 하는 색의 최솟값을 구하는 함수
    public static void find(int x, int y){ // 8X8 보드의 시작점 (x,y)
        // 끝점 (x+8, y+8)
        int end_x = x + 8;
        int end_y = y + 8;
        int count = 0; // 색 변환 카운트

        boolean TF = board[x][y]; // 시작점(x,y) 색상 

        for(int i=x; i<end_x; i++){
            for(int j=y; j<end_y; j++){

                // 올바른 색이 아닐 경우 카운트
                if(board[i][j] != TF){
                    count ++;
                }

                // 인접한 칸은 다른색.
                TF = (!TF);
            }
            // 줄 변환시에도 다른색/
            TF = (!TF);
        }

        // 시작점 색이 'W'일 경우, 'B'일 경우 중 최솟값
        count = Math.min(count, 64-count);

        // 이전 8X8에서 구한 값보다 최솟값인가.
        min = Math.min(min, count);
    }

---

고려해야하는 8X8 보드의 모든 경우의 수를 탐색하여 갱신된 최종 min 값을 출력한다.

        // 찾아야 하는 경우의 수
        int find_x = N - 7;
        int find_y = M - 7;

        for(int i=0; i<find_x; i++){
            for(int j=0; j<find_y; j++){
                find(i, j);
            }
        }

        bw.write(min+" ");
        bw.flush();
        bw.close();

---

전체 소스코드

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

public class Main{


    public static boolean[][] board;
    public static int min = 64;

    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());
        int N = Integer.parseInt(st.nextToken()); // 가로 길이
        int M = Integer.parseInt(st.nextToken()); // 세로 길이

        board = new boolean[N][M];

        // board 입력 받기
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken().toString();

            for(int j=0; j<M; j++){
                if(str.charAt(j) == 'W'){
                    board[i][j] = true;
                }
                else {
                    board[i][j] = false;
                }
            }
        }

        // 찾아야 하는 경우의 수
        int find_x = N - 7;
        int find_y = M - 7;

        for(int i=0; i<find_x; i++){
            for(int j=0; j<find_y; j++){
                find(i, j);
            }
        }

        bw.write(min+" ");
        bw.flush();
        bw.close();
    }


    // 주어진 8X8 보드에서 바꿔야 하는 색의 최솟값을 구하는 함수
    public static void find(int x, int y){ // 8X8 보드의 시작점 (x,y)
        // 끝점 (x+8, y+8)
        int end_x = x + 8;
        int end_y = y + 8;
        int count = 0; // 색 변환 카운트

        boolean TF = board[x][y]; // 시작점(x,y) 색상 

        for(int i=x; i<end_x; i++){
            for(int j=y; j<end_y; j++){

                // 올바른 색이 아닐 경우 카운트
                if(board[i][j] != TF){
                    count ++;
                }

                // 인접한 칸은 다른색.
                TF = (!TF);
            }
            // 줄 변환시에도 다른색/
            TF = (!TF);
        }

        // 시작점 색이 'W'일 경우, 'B'일 경우 중 최솟값
        count = Math.min(count, 64-count);

        // 이전 8X8에서 구한 값보다 최솟값인가.
        min = Math.min(min, count);
    }

} // Main

* 탐색해야할 총 경우의 수 : (N - 7) * (M - 7) * 2

* 색상이 두개인 만큼 boolean 배열을 이용.

* Math.min()을 사용하여 최솟값 구하기.

---

[참고 문서]

https://st-lab.tistory.com/101

[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]