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

문제 링크: 1018번 체스판 다시 칠하기

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

 

체스판과 같은 크기로, 2차원 int 배열을 먼저 다음과 같이 2개 더 만든다.

B로 시작하는 체스판, W로 시작하는 체스판에 대해서 각각의 칸에,

다시 칠해야 할 때 1, 다시 칠하지 않아도 될 때 0을 넣는다.

 

가로 8칸, 세로 8칸을 잘라낼 때 기준은 좌상단 모서리의 좌표로 설정했다.

이 좌표, 즉 board[row][col]의 row, col의 범위는 0<=row<=n-8, 0<=col<=m-8이다.

좌상단 모서리를 옮겨가면서 잘라낸 체스판에 들어있는 1의 개수를 모두 더하면 된다.

 

근데 이걸 그대로 하면 O(n^3)이 되니까...

지그재그로 1행 또는 1열만 갱신해나가면서 계산할 수 있다.

다만 구현이 너무 복잡해지니까 차선책으로 행이 바뀔 때는 새로 계산하고, 열이 바뀔 때는 1열만 갱신했다.

 

잘라낸 체스판 열 별로 계산한 값을 colsum에 저장하되,

colsum 길이를 m으로 설정해두고,

colsum의 합을 구할 때는 좌상단 모서리가 오른쪽으로 움직일 때마다 시작점과 끝점을 계속해서 1씩 증가시킨다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int getMin(int a, int b) {
	if (a < b) return a;
	else return b;
}

int getArrSum(int *arr, int start, int finish) {
	int sum = 0;
	for (int i = start; i <= finish; i++) {
		sum += arr[i];
	}
	return sum;
}

void getFirstColsum(int **arr, int i, int n, int m, int *colsum) {
	for (int c = 0; c < 8; c++) {
		for (int r = i; r < i + 8; r++) {
			colsum[c] += arr[r][c];
		}
	}
}

void getRepaint(int **arr, int n, int m, int *answer) {
	for (int i = 0; i <= n - 8; i++) {
		// 새 행에 진입할 때마다 colsum 새로 채우기
		int *colsum = (int *)(malloc(sizeof(int)*m));
		for (int t = 0; t < 8; t++) colsum[t] = 0;

		getFirstColsum(arr, i, n, m, colsum);
		*answer = getMin(getArrSum(colsum, 0, 7), *answer);

		int start = 0, finish = 7;
		for (int j = 1; j <= m - 8; j++) { // 자를 부분을 오른쪽으로 1칸 옮기기
			for (int t = i; t < i + 8; t++) {
				colsum[finish + 1] += arr[t][j + 7];
			}
			*answer = getMin(getArrSum(colsum, start + 1, finish + 1), *answer);
			start++; finish++;
		}
	}
}

void fill_arr(int **arr, int n, int m, char start, char **board) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if ((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
				if (board[i][j] == start) {
					arr[i][j] = 0;
				}
				else {
					arr[i][j] = 1;
				}
			}
			else {
				if (board[i][j] != start) {
					arr[i][j] = 0;
				}
				else {
					arr[i][j] = 1;
				}
			}
		}
	}
}

void printArr(int **arr, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << arr[i][j];
		}
		cout << '\n';
	}
}

int main() {
	/* 입력 */
	int n, m; cin >> n >> m;
	char **board = (char **)(malloc(sizeof(char *)*n));
	for (int i = 0; i < n; i++) {
		board[i] = (char *)(malloc(sizeof(char)*m));
		scanf("%s", board[i]);
	}

	/* arr_bw, arr_wb 만들기 */
	int **arr_bw = (int **)(malloc(sizeof(int *)*n));
	int **arr_wb = (int **)(malloc(sizeof(int *)*n));
	for (int i = 0; i < n; i++) {
		arr_bw[i] = (int *)(malloc(sizeof(int)*m));
		arr_wb[i] = (int *)(malloc(sizeof(int)*m));
		for (int j = 0; j < m; j++) {
			arr_bw[i][j] = 0;
			arr_wb[i][j] = 0;
		}
	}

	fill_arr(arr_bw, n, m, 'B', board);
	fill_arr(arr_wb, n, m, 'W', board);

	/* 다시 칠해야 하는 정사각형의 개수 구하기 */
	int answer = 65;
	getRepaint(arr_bw, n, m, &answer);
	getRepaint(arr_wb, n, m, &answer);

	cout << answer;

	return 0;
}