백준 1018번

문제 1018번

소스코드

import java.io.*;
import java.util.*;
public class boj1018 {
    public static boolean[][] arr;
    public 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());
        arr = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                if(input.charAt(j) == 'W'){
                    arr[i][j] = true;
                }else{
                    arr[i][j] = false;
                }
            }
        }
        for (int i = 0; i < n - 7; i++) {
            for (int j = 0; j < m - 7; j++) {
                search(i,j);
            }
        }
        System.out.println(min);
    }
    public static void search(int x, int y){
        int end_x = x+8;
        int end_y = y+8;
        int count = 0;
        boolean TF = arr[x][y];
        for (int i = x; i < end_x; i++) {
            for (int j = y; j < end_y; j++) {
                if(arr[i][j] != TF){
                    count++;
                }
                TF = (!TF);
            }
            TF = !TF;
        }
        count = Math.min(count, 64-count);
        min = Math.min(min, count);
    }
}

풀이 접근

1. 입력으로 정해진 배열에서 8x8배열을 잘라서 계산한다.
2. 흑과 백 2가지의 색상만 주어짐으로 2차원 boolean배열을 사용하여 흑일 때는 false를 백일 때는 true를 넣는다.
3. 8x8 배열이 만들어질 때 마다 search함수를 돌린다.
4. search함수 에서는 다시 칠해야 하는 부분을 count해 준다.
5. count가 반대 색칠의 경우의 수 보다 클 수도 있으므로, 마지막에 Math.min(count, 64-count)를 해준다.
6. 전역변수로 있는 min을 통해서 이전의 min 값이랑 비교해 count가 최소가 되는 값을 찾아서 저장한다.

문제 핵심

• 문제에서 원하는 알고리즘을 완성할 수 있는가!
• main함수가 아닌 class 안에 함수를 만들 경우에는 min과 boolean[][]배열을 전역변수로 선언 했는가