[백준] 1018. 체스판 다시 칠하기 (C++)

Key

보드판을 8*8 크기로 탐색을 반복하며 규칙을 찾는 문제

시작점이 바뀌어야하는 경우도 생각해야된다. 난 이걸 놓쳐서 한 번 틀렸다.

 

 

Idea

전체 크기 중 8*8만 탐색해야한다. 예를 들어 보드판 사이즈가 9*9라고 하면 다음과 같이 네번 탐색한다.

 

 

이때 시작점은 (0,0) (0,1) (1,0) (1,1) 이다. 이를 일반화해보면 시작점이 될 수 있는 범위는 (0~N-8, 0~M-8) 이 된다. 그리고 탐색 범위는 (시작점~시작점+8)이 된다. 따라서 식을 세워보면 다음과 같다.

for (int i=0; i<N-7; i++){
	for(int j=0; j<M-7; j++){
            for(int a=i; a<i+8; a++){
                for(int b=j; b<j+8; b++){
                    // 조건에 맞는지 체크	
                }
            }
    }
}

 

 

이제 조건에 맞는지 체크해야하는데, 시작점을 바꿔야 최솟값을 만족할 수도 있다. 따라서 케이스를 시작점을 바꿔야하는 경우와 그렇지 않은 경우로 나누어 생각해야한다.

 

이 그림을 보면 시작점은 (0,0)이고 값은 W이다. 다음 W는 (0,2), (0,4), (0,6), (1,1), (1,3), (1,5), (1,7)... 이를 일반화해보면

행, 열 인덱스가 모두 짝수이거나 홀수인 경우 즉, board[짝수][짝수]이거나 board[홀수][홀수]는 모두 시작점과 같아야한다. 행이나 열 인덱스 중 하나가 홀수인 경우엔 시작점 값과 달라야한다. 

 

식으로 나타내면 다음과 같다.

int start = arr[i][j];

if ((a+b)%2 == 0) {
	if (arr[a][b] != start) cnt++;
}
else {
	if (arr[a][b] == start) cnt++;
}

 

시작점 값이 바뀌는 경우도 있다. 등호만 반대로 바꿔주면 된다.

if ((a + b) % 2 == 0) {
	if (arr[a][b] == start) cnt2++;
}
else {
	if (arr[a][b] != start) cnt2++;
}

 

 

 

Code

나는 char 타입 배열을 만들면 좀 귀찮아서 그냥 입력받을 때 W면 1, 그렇지 않으면 2를 넣어 보드판을 완성했다.

#include <iostream>
using namespace std;


int arr[50][50] = { 0, };

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N = 0, M = 0;
	char input = ' ';

	cin >> N >> M;

	int minCnt = N*M;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> input;
			if (input == 'W') arr[i][j] = 1;
			else arr[i][j] = 2;
		}
	}

	// 시작점 범위
	for (int i = 0; i < N - 7; i++) {
		for (int j = 0; j < M - 7; j++) {
			int cnt = 0;
			int cnt2 = 0;
			// 탐색 범위
			for (int a = i; a < i + 8; a++) {
				for (int b = j; b < j + 8; b++) {

					int start = arr[i][j];

					// [짝수][짝수]는 모두 start, [홀수][홀수]는 모두 start. 나머지는 start이 아니어야함. 
					// 그렇지 않으면 카운트
						if ((a+b)%2 == 0) {
							if (arr[a][b] != start) cnt++;
						}
						else {
							if (arr[a][b] == start) cnt++;
						}

					// 반대의 경우 (시작점을 바꿔야하는 경우)
						if ((a + b) % 2 == 0) {
							if (arr[a][b] == start) cnt2++;
						}
						else {
							if (arr[a][b] != start) cnt2++;
						}
				}
			}

			minCnt = min(minCnt, min(cnt, cnt2));
		}
	}

	cout << minCnt << "\n";
	

	return 0;
}