[BaekJoon/백준] 1018번

이 문제는 좀 재밌었다.

 

문제 이해가 안돼서 힘들었던 거 빼고 ㅋㅋ..

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

public class Main {
    static int N, M;
    static boolean[][] arr, arr_copy;
    static int count=0, key=2500; // count를 재활용하고, key에 저장하여 사용.

    public static void main(String args[]) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tok = new StringTokenizer(br.readLine());
        N = Integer.parseInt(tok.nextToken());
        M = Integer.parseInt(tok.nextToken());

        // B = true, W = false로 저장.
        arr = new boolean[N][M];
        arr_copy = new boolean[N][M];

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                if(str.charAt(j)=='B') {
                    arr[i][j] = true;
                    arr_copy[i][j] = true;
                }
                else {
                    arr[i][j] = false;
                    arr_copy[i][j] = false;
                }
            }
        }
        do_job(false);
        do_job(true);

        if(key==2500)
            System.out.print(0);
        else
            System.out.print(key);
    }

    public static void do_job(boolean isReverse) {
        // 8 x 8 로 잘라야함.
        for(int x=0; x<= N-8; x++) {
            for(int y=0; y <= M-8; y++) {
                //오른쪽과 오른쪽아래 값, 대각선값 확인을 위해 크기 하나씩 줄인 값 까지만
                if(isReverse) {
                    //리버스
                    arr[x][y] = !arr[x][y];
                    count++;
                }
                for(int i=x; i<x+8-1; i++) {
                    for(int j=y; j<y+8-1; j++) {
                        if(arr[i][j]==arr[i][j+1]) {
                            arr[i][j + 1] = !arr[i][j];
                            count++;
                        }
                        if(arr[i][j]==arr[i+1][j]) {
                            arr[i+1][j] = !arr[i][j];
                            count++;
                        }
                        if(arr[i][j]!=arr[i+1][j+1]) {
                            arr[i+1][j+1] = arr[i][j];
                            count++;
                        }
                    }
                }
                if(key>count)
                    key=count;
                count=0;
                for(int i =0; i<N; i++) {
                    for(int j =0; j<M; j++) {
                        arr[i][j] = arr_copy[i][j];
                    }
                }
            }
        }
    }
}

 

내 방식은 2x2 로 나눠서 검사하는 방식이라, 검사 도중 중복검사가 많다.

 

중복없이 일자로 검사하는 방식이 훨씬 빠를 것이다..

->

∙ 본인자체와 오른쪽값만 검사하고, 행이 이동되었을 때에는 위의 행의 첫번째 값과 검사하여 세팅하고 다시 동일하게 진행.

(이때, if 문을 통해 i값이 0보다 클 때만, 즉 첫째 행에는 위의 행이 없으니 i가 1부터 위의 행의 첫번째 값과 검사하여 세팅하도록 진행)