백준_1018번_체스판 다시 칠하기_자바

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

1018번: 체스판 다시 칠하기

 

백준_1018번_체스판 다시 칠하기_자바

 

해당 문제의 경우 완전 탐색 문제라고 볼 수 있으며,

 

조건을 정리하면,

 

1. 8x8크기의 체스판을 만든다.

2. 체스판에  white나 black색이 교차하며 칠해져 있는지 확인한다.

3. 잘못 칠해진 판의 개수를 구한다.

4. 8x8보다 클경우 8x8크기로 잘라서 구하며, 여러 경우에서 나온 잘못 칠해진 판의 개수중 제일 작은 경우를 출력한다.

이렇게 정리 할 수 있습니다.

 

실제 구현한 로직은 아래와 같습니다.

 

 

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


public class Main {

    static int min = Integer.MAX_VALUE;
    static char[][] c;

    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());

        c = new char[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < m; j++) {
                c[i][j] = line.charAt(j);
            }
        }

        int maxN = n-7;
        int maxM = m-7;

        for (int i = 0; i < maxN; i++) {
            for (int j = 0; j < maxM; j++) {
                findStart(i,j);
            }
        }

        System.out.println(min);

    }

    private static void findStart(int x, int y) {
        int maxX = x+8;
        int maxY = y+8;
        int cnt=0;

        char match = c[x][y];

        for (int i = x; i < maxX; i++) {
            for (int j = y; j < maxY; j++) {

                if(match != c[i][j]){
                    cnt++;
                }

                match = match == 'W'? 'B':'W';
            }
            match = match == 'W'? 'B':'W';
        }

        cnt = Math.min(cnt , 64-cnt);
        min = Math.min(min,cnt);

    }
}