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

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

풀기전 로직 생각

1. 입력받을 N과 M을 입력받는다
2. 입력받은 N과 M으로 2차원 배열을 동적 할당시켜준다.
3. 값을 13 13으로 입력받았다 치더라도 8X8크기로 잘라서 해야하므로 for문을 n-8과 m-8로 이중for문 설정
4. 체스판 검사 로직을 만들어서 W를 바꾼값과 B를 바꾼값을 비교하여 적은값을 추출
5. 8X8검사를 한것들중 가장 작은값 하나만을 추출 

---

코드

#include <iostream>
#include <algorithm> // min 함수
using namespace std;


int ChessMinChange(char** WB, int startX, int startY) {
	int changesW = 0, changesB = 0; //W를 바꾼횟수와 B를 바꾼횟수

	//로직은 매개변수로 받아온 Start 좌표시작위치에서 8X8로 탐색한다.
	//해당 위치의 값과 짝수위치와 홀수 위치의 값을 비교한다.
	//체스판은 짝수위치는 같은 값이어야하고 홀수위치는 다른값이어야 하므로 W로 시작할때 짝수위치가 W가 아니면 W를 바꾸고 B도 이와동일
	//홀수 위치는 위와 반대로 


	for (int i = startX; i < startX + 8; i++) { //시작 위치에서 최대8칸
		for (int j = startY; j < startY + 8; j++) { //시작 위치에서 최대8칸
			if ((i + j) % 2 == 0) { // 체스판의 짝수 위치
				if (WB[i][j] != 'W') //W로 시작했을때 짝수위치에 W가 아닐경우 WB[0][0]이 W인데 WB[0][2]가 W가 아니면 이를 바꾸므로 W를 증가
					changesW++;
				if (WB[i][j] != 'B') //B로 시작했을때 짝수위치에 B가 아닐경우 위와 똑같이
					changesB++;
			}
			else { // 체스판의 홀수 위치
				if (WB[i][j] != 'B') //만약 WB[0][1]이 B인데 WB[0][3]이 W면 해당위치를 바꿔야하므로 W를 증가
					changesW++;
				if (WB[i][j] != 'W') //위와 똑같이
					changesB++;
			}
		}
	}
	return min(changesW, changesB); // W를 바꾼것과 B를 바꾼것중 더 적은것을 min함수로 반환
}

int main() {
	ios::sync_with_stdio(0);
	cout.tie(nullptr);
	cin.tie(nullptr);
	//첫줄에는 n과 m을 8보다 크같 50보다 작같 자연수 입력
	//둘째부터 n개 줄 m개의 갯수로 이루어진 wbwb로 나옴


	int n, m;
	std::cin >> n >> m; //n과 m을 입력받는다.
	if (!(n >= 8 && n <= 50) || !(m >= 8 && m <= 50)) //범위 맞추기
		return 0;

	char** WB = new char* [n]; // 세로길이 n만큼 배열 할당
	for (int i = 0; i < n; i++) {
		WB[i] = new char[m]; // 가로길이 m만큼 배열 할당
	}

	//memset(WB, 0, sizeof(WB)); //메모리 0으로 초기화

	for (int i = 0; i < n; i++) { //WB입력을 받음
		for (int j = 0; j < m; j++) {
			std::cin >> WB[i][j];
		}
	}
	
	int minCount = 64;; //8X8 체스판 검사이므로 최대 변경횟수는 64번 작게 해버리면 로직이 꼬이므로 최대값으로 설정
	for (int i = 0; i <= n - 8; i++) {
		for (int j = 0; j <= m - 8; j++) { //8X8로 검사
			minCount = min(minCount, ChessMinChange(WB, i, j)); //지금까지 비교한 값중 가장 작은값이 최종적으로 나오게됨
		}
	}
	cout << minCount; // 최소 변경 횟수 출력

	//delete
	for (int i = 0; i < n; i++) {
		delete[] WB[i];
	}
	delete[] WB;

	return 0;
}

 

결과

예제 입력 1 복붙 결과

예제1

예제 입력 2 복붙 결과

예제2

예제 입력 4 복붙 결과

예제4

 

어느정도 로직을 작성해준 후 GPT의 도움으로 작성했습니다.