[백준] 1018번 - 체스판 다시 칠하기 (java)

NxM 체스판 중 8x8 영역을 골라 각 칸을 하얀색과 검정색을 지그재그로 칠해야 할 때 최소 몇번을 칠해야 하는지를 묻는 문제이다.

---

for(int i=0; i<=N-8; i++){
	for(int j=0; i<=M-8; j++){
    	...
        for(int x=0; x<8; x++){
        	for(int y=0; y<8; y++){
            	...
            }
        }
    }
}

문제 유형이 브루트 포스인 만큼 결국은 모든 영역을 확인해야 하기에
NxM 체스판의 모든 영역을 탐색하는 이중포문 하나와
선택된 8x8 영역 중 색을 칠해야 하는 칸의 갯수를 탐색하는 이중포문 하나
-> 합쳐서 4중 포문을 이용해야 한다.

i와 j는 NxM의 영역. N과 M은 8보다 크거나 같은 수이므로 8x8영역을 선택하려면 N-8과 M-8의 영역보다 작거나 같은 영역만큼의 횟수만 탐색하면 된다.

이때 x와 y는 선택된 8x8 영역에서의 계산을 의미한다.

---

for(int i=0; i<=N-8; i++){
	for(int j=0; j<=M-8; j++){
        int cntW = 0;	// 새로 칠해야 하는 White의 수
        int cntB = 0;	// 새로 칠해야 하는 Black의 수
        for(int x=0; x<8; x++){
        	for(int y=0; y<8; y++){
            	char expectedW = ((x + y) % 2 == 0) ? 'W' : 'B';
                // 왼쪽 위 칸을 W라고 가정 했을때의 x, y칸의 색
                char expectedB = ((x + y) % 2 == 0) ? 'B' : 'W';
                // 왼쪽 위 칸을 B라고 가정 했을때의 x, y칸의 색
                        
                if(arr[i+x][j+y] != expectedW){ cntW++; }
                if(arr[i+x][j+y] != expectedB){ cntB++; }
                    }
                }

색을 정하는 기준은 1행1열. 즉 맨 첫번째 칸이 White인지, Black인지를 먼저 판별하여 짝수/홀수로 나머지 칸을 구별하는 방식으로 시작한다.

x와 y를 합쳐 2로 나눈 나머지가 0이냐 1이냐에 따라 짝수칸/홀수칸이 갈린다.
맨 첫번째 칸을 x=0, y=0 으로 본다면 2와 나누었을때 나머지가 0이고, 이때 해당 칸이 White인지, Black인지에 따라 expectedW, expectedB 변수로 각각 저장한다.

예를들면 맨 첫번째 칸이 White였다면 expectedW는 W가, expectedB는 B가 저장된다.
이제부터 (x+y)%2==0인 모든 칸의 expectedW에는 W가 저장된다.
이렇게 하면 8x8영역은 깔끔한 지그재그 모양으로 색이 칠해진다.

arr[i+x][j+y] 배열은 전체 NxM 체스판 영역이고, 전체영역 체스판에서의 x, y에 해당하는 칸이 W이냐 B냐에 따라 새로 칠해야 할 칸의 갯수를 증가시켜야 한다.

칸을 W로 새로 칠해야 하면 cntW를, B로 새로 칠해야 하면 cntB를 증가시킨다.
이는 arr[i+x][j+y]칸과 expected변수로 설정된 칸의 색이 서로 다른지를 확인해서 알아낼 수 있다.

하나의 8x8영역이 끝날때마다 비교하며 가장 최소로 칸을 칠해야 하는 칸 수를 선별할 수 있다.

위 내용을 바탕으로 설계한 코드는 다음과 같다.

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        char[][] arr = new char[N][M];
        
        for(int i=0; i<N; i++){
            String s = sc.next();
            for(int j=0; j<M; j++){
                char c = s.charAt(j);
                arr[i][j] = c;
            }
        }
        
        int result = 63;	// 가능한 최대 갯수
        for(int i=0; i<=N-8; i++){
            for(int j=0; j<=M-8; j++){
                int cntW = 0;	// 새로 칠해야 하는 White의 수
                int cntB = 0;	// 새로 칠해야 하는 Black의 수
                for(int x=0; x<8; x++){
                    for(int y=0; y<8; y++){
                        char expectedW = ((x + y) % 2 == 0) ? 'W' : 'B';
                        char expectedB = ((x + y) % 2 == 0) ? 'B' : 'W';
                        // 왼쪽 위 칸의 색을 판별하고,
                        // 이에 맞는 깔끔한 지그재그 체스판 제작
                        
                        if(arr[i+x][j+y] != expectedW){ cntW++; }
                        if(arr[i+x][j+y] != expectedB){ cntB++; }
                        // NxM 체스판에서 (i+x, j+y)칸과 (x, y)칸을 비교
                        // 색이 다르면 칠해야 하는 색을 카운트
                    }
                }
                result = Math.min(result, Math.min(cntW, cntB));
            }
        }
        
        System.out.println(result);
        
    }
}

맞았습니다!!