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

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

1018번: 체스판 다시 칠하기

---

• 풀이방법[알고리즘]

M*N의 박스에서 8*8 크기의 정사각형을 자르고, 흰검이 번갈아 나타나는 체스판으로 만들기 위한 최소의 수정을 구하는 문제. for문 계속 돌리면서 완탐으로 풀었다. CHAR로 입력받으면 if문으로 계속 분기처리해야 할 것 같아서 B는 0, W는 1로 설정하여 MAP을 그려주었다. 입력받은 값에서, 8 * 8로 자를 때 START POINT( 왼쪽상단 꼭짓점)를 구한 다음, 잘라낸 맵에서 색을 변경하는 작업을 진행해주었다.

값을 변경할 때는 start point를 변경시키지 않고 작업하는 경우와, 변경하고 작업하는 경우 2개로 나누어서 진행하였다. 우측과 하단만 확인하고 내려가면 되는 구조라 move는 {{0,1},{1,0}}으로 설정하고 이동한 값을 확인해 현재 값과 같을 때, 변경시켜주었다.  하단 값은 첫 값만 확인하면 그대로 이어지는 것이라서 우측과 하단을 둘다 비교할 필요가 없었다. 따라서 r값이 0일 때만 하단의 값과 동일한지 확인하는 로직으로 변경하였다. 값은 0과 1로 설정했기 때문에, 2로 나눈 나머지로 값을 처리해주었다. 붙어있는 값이 동일한 경우 (현재 값+1)%2로 값을 변경해주었다. 만약 count값이 기존의 최소변경값보다 크다면 그 경우는 더 볼 필요가 없기 때문에 max_value로 리턴하였다. start point를 변경하고 진행하는 경우는 결과값에 +1를 해주어야 하는데 오버플로우가 발생하여서 최소값으로 나온기 때문에, max_value가 아닐때만 1을 더해주었다.

처음 실행시켰을 때, 4번 테스트케이스만 틀려서 당황했는데, captureMap을 원상복구하지 않아서 틀렸었다. 나머지 6개의 테스트케이스는 우연히 값을 잘 찾아온 경우였었다..

 

package newAlgorithm;

import java.io.*;
import java.util.*;

public class P3_BJ1018 {
    static int answer, M, N, map[][];

    public static void main(String[] args) throws IOException {
        //M*N 그림 -> 8*8 검흰이 번갈아서 색칠. 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        answer = Integer.MAX_VALUE;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        //입력값 받아서 그리기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            //b=0 w=1;
            for (int j = 0; j < M; j++) {
                if (str.charAt(j) == 'B') {
                    map[i][j] = 0;
                } else {
                    map[i][j] = 1;
                }//if
            }//for_2
        }//for_1

        //startPoint 정하기
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                switchColor(i, j);
            }
        }
        System.out.println(answer);
    }//MAIN

    static void switchColor(int r, int c) {
        //일단 0,0 ~ 8,8 까지 떼어내고, 왼쪽이 검정인걸로 1번, 흰색인걸로 1번확인
        //0,1 ~8,9 ~~~~ 0,N-8 8,N까지
        //이중for문으로

        int[][] captureMap = new int[8][8];
        int[][] origMap = new int[8][8];
        for (int i = r; i < r + 8; i++) {
            for (int j = c; j < c + 8; j++) {
                origMap[i - r][j - c] = map[i][j];
                captureMap[i - r][j - c] = map[i][j];
            }//for_1
        }//for_2

        //그린 맵에서 BW 변경테스트
        ///왼쪽 위에서부터 확인하고 내려오니까 오른쪽이랑 아래만 확인하면 된다.
        int orig = checkMin(captureMap);
        answer = Math.min(orig, answer);


        //원상복구 후 첫번째 값 바꿔서 돌리기
        for (int i = 0; i < 8; i++) {
            captureMap[i] = origMap[i].clone();
        }
        captureMap[0][0] = (captureMap[0][0] + 1) % 2;
        int change = checkMin(captureMap);
        //위에서 값 바꿨으니까+1;
        if (change != Integer.MAX_VALUE) {
            change += 1;
        }
        answer = Math.min(change, answer);
    }//checkMin

    static int checkMin(int[][] captureMap) {
        int min = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                //일단 오른쪽만 확인하고, j가 0이면 아래도 확인
                int nextR = i + 1;
                int nextC = j + 1;
                if (j == 0 && nextR < 8 && captureMap[nextR][j] == captureMap[i][j]) {
                    captureMap[nextR][j] = (captureMap[nextR][j] + 1) % 2;
                    min++;

                }
                if (nextC < 8 && captureMap[i][nextC] == captureMap[i][j]) {
                    captureMap[i][nextC] = (captureMap[i][nextC] + 1) % 2;
                    min++;
                }
                if (min >= answer) {
                    return Integer.MAX_VALUE;
                }
            }//for2
        }//for1
        return min;
    }

}//CLASS