[Java] 4단계. 체스판 다시 칠하기 [1018번]

• 예제 입력1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• 예제 출력1

1

• 예제 입력2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

• 예제 출력2

12

 

• 예제 입력3

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

• 예제 출력3

0

• 예제 입력4

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

• 예제 출력4

31

• 예제 입력5

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

• 예제 출력5

0

 

---

 

• 문제 접근
  • 8 * 8 크기의 체스판을 만드는 것이 목적
  • 체스판은 검은칸과 흰칸이 번갈아 칠해져있어야 함
  • 가장 왼쪽 위의 색을 기준으로 바로 아래 사각형은 반대 색깔
  • 시간 복잡도가 $O\left (N^{4}\right )$ 되기는 하지만, N과 M의 범위는 8이상 50이하이므로 최대 연산 횟수는 6,250,000 $\left (  0.0625초\right ) $
• 문제 해결
  • 8 * 8 크기의 화이트로 시작할 때의 체스판, 블랙으로 시작할 때의 체스판을 준비
  • 4중 for문으로 최소값 검증
    • row는 N-8까지, col은 M-8까지 반복
    • → x=0, y=0부터 시작하여 완성된 체스판과 비교하여 다를 경우 count 증가
• 슈도 코드

N(줄 개수 저장), M(열 개수 저장)
A[N][M] (2차원 char 배열 선언]
blackChess[8][8], whiteChess[8][8] (블랙 시작, 화이트 시작 체스판 선언)
for(i = 0 ~ 7까지 반복){
	for(j = 0 ~ 7까지 반복){
		if((i+j) % 2 == 0){
			blackChess[i][j] <- 'B' 추가
			whiteChess[i][j] <- 'W' 추가
		} else{
			blackChess[i][j] <- 'W' 추가
			whiteChess[i][j] <- 'B' 추가
		}
	}
}
minCount (최댓값 저장)
for(row = 0 ~ N - 7까지 반복){
	for(col = 0 ~ M - 7까지 반복){
		blackCount = 0 (블랙으로 시작하는 체스판 변화 횟수 체크)
		whiteCount = 0 (화이트로 시작하는 체스판 변화 횟수 체크)
		for(int x = 0 ~ 7까지 반복){
			for(int y = 0 ~ 7까지 반복){
				if(A[row+x][col+y] != blackChess[x][y]){
					blackCount 1 증가
				}
				if(A[row+x][col+y] != whiteChess[x][y]){
					whiteCount 1 증가
				}
			}
		}
		minCount = 최솟값(minCount, 최솟값(blackCount, whiteCount))
	}
}

• 코딩하기

package Step12;

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

public class No4 {
    public static void main(String[] args) throws Exception{
        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());
        char[][] chess = new char[N][M];
        for(int i = 0; i < N; i++){
            chess[i] = br.readLine().toCharArray();
        }
        char[][] blackChess = new char[8][8];
        char[][] whiteChess = new char[8][8];
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++){
                if((i + j) % 2 == 0){
                    blackChess[i][j] = 'B';
                    whiteChess[i][j] = 'W';
                } else{
                    blackChess[i][j] = 'W';
                    whiteChess[i][j] = 'B';
                }
            }
        }
        int minCount = Integer.MAX_VALUE;
        for(int row = 0; row <= N - 8; row++){
            for(int col = 0; col <= M - 8; col++){
                int blackCount = 0;
                int whiteCount = 0;
                for(int x = 0; x < 8; x++){
                    for(int y = 0; y < 8; y++){
                        if(chess[row + x][col + y] != blackChess[x][y]){
                            blackCount++;
                        }
                        if(chess[row + x][col + y] != whiteChess[x][y]){
                            whiteCount++;
                        }
                    }
                }
                minCount = Math.min(minCount, Math.min(blackCount, whiteCount));
            }
        }
        System.out.println(minCount);
    }
}