[BAEKJOON] 1018번 체스판 다시 칠하기

 

---

아래 그림들은 위의 입력 예제에서 N : 10, M : 13일 때의 경우이다.

문제를 풀어보기 전에 완벽한 체스판의 8*8 윈도우가 있다고 가정하자.

물론 맨 왼쪽 시작이 B인지 W인지 두 가지 모두 고려해야 한다.

이 아래 하늘색의 윈도우를 한 칸씩 이동하며 주어진 체스판의 범위를 넘어가지 않는 한 탐색할 수 있도록 조정한다.

만약 주어진 체스판과 윈도우와 일치하지 않는 칸이 많다면 최소 개수를 만족하지 못 하므로 윈도우를 다음 칸으로 옮겨 탐색을 시작한다.

윈도우를 이동할 수 있는만큼 이동할 때까지 반복하며 주어진 체스판과 윈도우의 일치하지 않는 칸의 최소 개수를 구하면 된다.

 

 

 

※ 여기서 고려해야 할 점!

위에서 언급했듯이 윈도우의 맨 왼쪽 윗 칸이 B로 시작할 때와 W로 시작할 때 두 경우를 모두 고려하여 판단해야 한다.

즉, 아래 그림에서는 18번의 과정으로 윈도우와 비교하였는데 사실은 B로 시작할 때 18번, W로 시작할 때 18번을 비교하여야 한다는 것이다.

반복문은 두 번 돌릴 것이냐? 아니다!

아래 그림을 보자.

윈도우의 맨 왼쪽 위 시작이 W일 경우는 짝수행이 WBWBWBWB로, 홀수행이 BWBWBWBW로 반복되고, 맨 왼쪽 위 시작이 B일 경우는 짝수행이 BWBWBWBW로, 홀수행이 WBWBWBWB로 반복된다.

 

String 문자열을 만들어 윈도우의 행이 W로 시작할 때와 B로 시작할 때의 규칙을 적용해보자.

String wStart="WBWBWBWB", bStart="BWBWBWBW";

이와 같이 문자열을 생성하여

1. 맨 왼쪽 위 시작이 W일 때 비교해야 할 행이 짝수일 경우 해당 행은 W로 시작하고, 해당 행이 홀수일 경우 B로 시작

2. 맨 왼쪽 위 시작이 B일 때 비교해야 할 행이 짝수일 경우 해당 행은 B로 시작하고, 해당 행이 홀수일 경우 W로 시작

크게 두 과정을 세분하여 생각해볼 수 있다.

 

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

public class Main {
	static int N, M, cnt, min=100;
	static String arr[][], wStart="WBWBWBWB", bStart="BWBWBWBW";
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new String[N][M];
		for(int i=0; i<N; i++) {
			arr[i] = br.readLine().split("");
		}
        // 윈도우가 움직일 수 있는 범위
		for(int i=0; i<N-8+1; i++) {
			for(int j=0; j<M-8+1; j++) {
				int temp = check(i, j);
				min = min>temp?temp:min; // 반환된 값과 최소값 비교하여 더 작은 수 저장!
			}
		}
		System.out.println(min);
	}
	private static int check(int x, int y) {
		int wStartCnt=0; // 윈도우 맨 왼쪽 윗 칸이 W로 시작할 때 일치하지 않는 값 카운트
        int bStartCnt=0; // 윈도우 맨 왼쪽 윗 칸이 B로 시작할 때 일치하지 않는 값 카운트
		for(int i=x; i<x+8; i++) {
			int index=0; // 전역변수인 wStart와 bStart의 문자열 인덱스
			for(int j=y; j<y+8; j++, index++) {
				// w로 시작
				// 짝수행일 경우 W로 시작
				if(i%2==0 && !arr[i][j].equals(String.valueOf(wStart.charAt(index)))) {
					wStartCnt++;
				}
				// 홀수행일 경우 B로 시작
				if(i%2!=0 && !arr[i][j].equals(String.valueOf(bStart.charAt(index))))
					wStartCnt++;
				
				// B로 시작
				// 짝수행일 경우 B로 시작
				if(i%2==0 && !arr[i][j].equals(String.valueOf(bStart.charAt(index))))
					bStartCnt++;
				// 홀수행일 경우 W로 시작
				if(i%2!=0 && !arr[i][j].equals(String.valueOf(wStart.charAt(index))))
					bStartCnt++;
			}
		}
        // W로 시작했을 때의 차이, B로 시작했을 때의 일치하지 않는 값 중 최솟값 반환
		return Math.min(wStartCnt, bStartCnt);
	}
}

[출처]

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

1018번: 체스판 다시 칠하기