[BOJ] 1018 "체스판 다시 칠하기" 문제 풀이 & 소스 코드 With C/C++

#INFO

난이도 : SILVER5

알고리즘 유형 : BruteForce

출처 : 1018번: 체스판 다시 칠하기 (acmicpc.net)

1018번: 체스판 다시 칠하기

---

#SOLVE

모든 경우의 수를 대입하는 브루트포스 알고리즘을 이용해 문제를 풀이하였습니다.

우선, 맨 앞이 검정으로 시작하는 8 x 8 타일 black_board와 하얀색으로 시작하는 8 x 8 타일 white_board 를 string 배열을 이용해 선언해 줍니다.

string black_board[8] =  { 
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB" 
							};
	
string white_board[8] = { 
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW" 
							};

 

다음으로 N * M 타일 보드의 값과 black_board의 값을 비교하는 B_CNT 함수와 white_board의 값을 비교하는 W_CNT 함수를 선언합니다.

B_CNT, W_CNT 함수는 N * M 보드에서 좌표값을 받아와 순차적으로 탐색을 진행하여 서로 다른 값이 존재하면 cnt 값을 증가시키는 기능을 수행합니다.

예를들어 3 * 3 타일의 black_board와 5 * 5 타일의 보드를 B_CNT 함수로 비교한다고 가정 시 , 서로 다른 색깔이 총 7개가 존재하기에, 7의 값을 리턴합니다.

int B_Cnt (int x, int y) {
	int cnt = 0;
	for (int i = 0 ; i < 8 ; i++) {
		for (int j = 0 ; j < 8 ; j++) {
			if (black_board[i][j] != board[i+x][j+y]) 
				cnt++;
		}
	}
	return cnt;
}

int W_Cnt (int x, int y) {
	int cnt = 0;
	for (int i = 0 ; i < 8 ; i++) {
		for (int j = 0 ; j < 8 ; j++) {
			if (white_board[i][j] != board[i+x][j+y])
				cnt++;
		}
	}
	return cnt;
}

 

메인 함수에서는 모든 경우의 수를 탐색해 B_Cnt와 W_Cnt의 리턴값 중 더 작은 값을 min_val 변수에 초기화 시키면 됩니다.

	int min_val = 10000;
	for (int i = 0 ; i <= N - 8 ; i++) {
		for (int j = 0 ; j <= M - 8 ; j++) {
			int temp = min(B_Cnt(i, j), W_Cnt(i, j));
			if (temp < min_val)
				min_val = temp;
		}
	}

---

#CODE

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

char board[51][51];

string black_board[8] =  { 
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB" 
							};
	
string white_board[8] = { 
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW",
							"WBWBWBWB",
							"BWBWBWBW" 
							};

int B_Cnt (int x, int y) {
	int cnt = 0;
	for (int i = 0 ; i < 8 ; i++) {
		for (int j = 0 ; j < 8 ; j++) {
			if (black_board[i][j] != board[i+x][j+y]) 
				cnt++;
		}
	}
	return cnt;
}

int W_Cnt (int x, int y) {
	int cnt = 0;
	for (int i = 0 ; i < 8 ; i++) {
		for (int j = 0 ; j < 8 ; j++) {
			if (white_board[i][j] != board[i+x][j+y])
				cnt++;
		}
	}
	return cnt;
}

int main(){
	int N,M;
	cin >> N >> M;
	for (int i = 0 ; i < N ; i++) {
		for (int j = 0 ; j < M ; j++) {
			cin >> board[i][j];
		}
	}
	
	int min_val = 10000;
	for (int i = 0 ; i <= N - 8 ; i++) {
		for (int j = 0 ; j <= M - 8 ; j++) {
			int temp = min(B_Cnt(i, j), W_Cnt(i, j));
			if (temp < min_val)
				min_val = temp;
		}
	}
	
	cout << min_val << endl;
	return 0;
}