알고리즘: 백준 1018번 체스판 다시칠하기(feat. c++)

백준 1018번 링크입니다. 

1018번: 체스판 다시 칠하기

 

 

 

B로 시작하는 8 x 8 완성된 체스판을 chess1 

W로 시작하는 8 x 8 완성된 체스판을 chess2

내가 입력받을 잘못된 체스판을 wrong_chess라고 하자 

 

 

wrong_chess의 행과 열을 변화시켜 가면서 chess1과 chess2와 비교한다. 

 

 

chess1과 비교했을 때 잘못된 값의 갯수 = wrong_count1

chess2과 비교했을 때 잘못된 값의 갯수 = wrong_count2일때

 

 

두 값중에 더 작은 값을 찾아 가면서 최솟값을 찾는다. 

 

#include<iostream>
using namespace std;
int main() {

	int n, m;
	cin >> n;
	cin >> m;



// 8 x 8 체스판 만들기 
	string* chess1 = new string[8];
	string* chess2 = new string[8];

	for (int i = 0; i < 8; i++) {

		if (i % 2 == 0) {
			chess1[i] = "BWBWBWBW";
			chess2[i] = "WBWBWBWB";

		}
		else {
			chess1[i] = "WBWBWBWB";
			chess2[i] = "BWBWBWBW";

		}
	}

// 가져올 n x m 체스판
	string* wrong_chess = new string[n];

	for (int i = 0; i < n; i++) {

		cin >> wrong_chess[i];

	}


	int min = 10000;
	
    
    // 내가 만든 8 x 8 체스판과 내가 가져온 잘못된 체스판을 비교하면서 wrong_count를 쌓는다.
    
	for (int x = 0; x <= n - 8; x++) {
		for (int y = 0; y <= m - 8; y++) {
			int wrong_count1 = 0;  // chess1과 비교했을때 잘못된 값
			int wrong_count2 = 0;  // chess2과 비교했을때 잘못된 값
			
			for (int i = 0; i < 8; i++) {

				for (int j = 0; j < 8; j++) {
					if (chess1[i][j] != wrong_chess[i + x][j + y]) {
						wrong_count1 += 1;

					}

					if (chess2[i][j] != wrong_chess[i+x][j+y]) {
						wrong_count2 += 1;
					
					}

				}
			}
		
			int wrong_count;
			if (wrong_count1 < wrong_count2) {
				wrong_count = wrong_count1;
			}
			else {
				wrong_count = wrong_count2;
			}
            // wrong_count1와 wrong)_count2 중 더 작은 값을 찾는다.
            
			if (min > wrong_count) {
				min = wrong_count;
			}
            // 최소값 비교
            
		}
	}

	
    cout << min<< endl;


	return 0;
}