백준 1018 체스판 다시 칠하기(JAVA)

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

1018번: 체스판 다시 칠하기

 

 

 

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.StringTokenizer;

public class Main_BJ_1018_체스판다시칠하기 {
    static int n, m, ans;
    static char[][] map;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<m; j++){
                map[i][j] = str.charAt(j);
            }
        }

        ans = Integer.MAX_VALUE;
        for(int i=0; i<n-7; i++){
            for(int j=0; j<m-7; j++){
                find(i, j);
            }
        }
        System.out.println(ans);
    }//main
    private static void find(int x, int y){
        int cnt = 0;
        char cur = map[x][y];
        for(int i=x; i<x+8; i++){
            for(int j=y; j<y+8; j++){
                if(cur != map[i][j])
                    cnt++;

                if(cur == 'B')
                    cur='W';
                else cur='B';
            }
            if(cur == 'B')
                cur='W';
            else cur='B';
        }
        cnt = Math.min(cnt, 64-cnt);
        ans = Math.min(cnt, ans);

    }//find
}

이 문제는 완탐의 기본적인 문제라고 할 수 있다.

8칸씩 확인해야하므로 n-7, m-7위치까지 순회하고,

find 함수에서 순회하면서 바꿔야 하는 칸을 센다.

이때, 기준점을 왼쪽 최상단으로 잡는데, 그대로 잡을 것인지 아님 반대로 잡을 것인지 정해야 한다.

 

나는 그대로 잡는 것으로 두고 했다!

그리고, 반대를 기준으로 잡을 때는 64칸 중 셌던 칸을 빼면 되므로 간단하게 구할 수 있다.

이 부분이 헷갈렸는데, 생각해보면 당연한거더라....