백준 BOJ 1018번

---

접근 방법

• 체스판 크기에 상관없이 가장 적게 칠할 수 있는 8 x 8 크기를 찾아야 한다.
• 경우의 수는 (가로칸 개수 - 7) x (세로칸 개수 - 7)
• 첫번째 칸이 검은색일 경우, 하얀색일 경우가 있다.

→ 결과적으로 경우의 수는 2 X (가로칸 개수 -7) X (세로칸 개수 - 7)

 

모든 경우의 수를 탐색해서 최소를 찾아야 하므로 Brute force 방식을 사용해야 한다.

 

Brute force 브루트 포스

완전탐색 알고리즘으로, 가능한 모든 경우의 수를 탐색하면서 조건에 맞는 결과를 가져온다.

brute force 방식의 기본적인 접근 방법은 해가 존재할 가능성이 있는 모든 영역을 탐색하는 방법이다.

 

장점

• 알고리즘을 설계하고 구현하기 쉽다.
• 예외 없이 100% 정답을 찾아낼 수 있다.

단점

• 당연하게도 시간적으로 비효율적이다.
• 공간적으로도 비효율적이다.

---

코드

import java.util.*;

public class Main {
    public static boolean[][] arr;
    public static int min = 64;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        arr = new boolean[N][M];
				
		//입력
        for(int i = 0; i < N; i++){
            String str = in.next();
            for(int j = 0; j < M; j++){
                if(str.charAt(j) == 'W'){
                    arr[i][j] = true;
                } else {
                    arr[i][j] = false;
                }
            }
        }
        int row = N-7;
        int col = M-7;
        for(int i = 0; i < row; i++){
            for(int j = 0;j < col; j++){
                find(i, j);
            }
        }
        System.out.println(min);
        in.close();
    }
    public static void find(int x, int y){
        int count = 0;
        boolean first = arr[x][y]; //첫 칸의 색

        for(int i = x; i < x + 8 ; i++){
            for(int j = y; j < y + 8; j++){
                if(arr[i][j] != first){
                    count++;
                }
                first = !first;
            }
            first = !first;
        }	
		count = Math.min(count, 64 - count);
		min = Math.min(min, count);
    }
}