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

BOJ 1018번

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

백준 1018번 C++ 소스

1개열(column) 각각 1개씩 열(column)이 아니라 전체 8X8을 기준으로 놓고 브루트포스 해야한다. 

white와 black경우의 수 2개를 모두 다 구해봐야함.

예를들어 [0][0]이 B일때 black_check만 할것이 아니라 반드시 white_check도 해봐야 한다는 것.

첫 째자리를 W로 바꿨을 때 최적이 될 수 있기 때문이다.

체스판이니까 가로로 B,W,B,W이런식으로 된다는건 쉽게 알 수 있었는데 

 세로로도  B,W,B,W이렇게  가로처럼 엇갈리게 되야한다는걸 모르고 문제풀어서 꽤나 고생했었다. 

변수 i,j는 행(또는 열)을 하나씩 옮겨주는 변수임 

ex) [0]~[7]까지 조사가 끝났을 때 [1]~[8]까지 이렇게 옮겨주는 변수. 

이때 map1,map2는 배열의 범위 [0]~[7]을 초과하지 않게 잘 다뤄줘야함.

#include "pch.h"
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

char input_data[51][51];

int black_check(int x, int y,int i, int j)
{
	char map1[8][8] = {{'B','W','B','W','B','W','B','W'},{'W','B','W','B','W','B','W','B'},
	{'B','W','B','W','B','W','B','W'}, {'W','B','W','B','W','B','W','B'},
	{'B','W','B','W','B','W','B','W'}, {'W','B','W','B','W','B','W','B'},
	{'B','W','B','W','B','W','B','W'},{'W','B','W','B','W','B','W','B'} };

	if (input_data[x][y] != map1[x-i][y-j])
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int white_check(int x, int y, int i, int j)
{
	char map2[8][8] = {{'W','B','W','B','W','B','W','B'},{'B','W','B','W','B','W','B','W'},
	{'W','B','W','B','W','B','W','B'} ,{'B','W','B','W','B','W','B','W'},
	{'W','B','W','B','W','B','W','B'} ,{'B','W','B','W','B','W','B','W'},
	{'W','B','W','B','W','B','W','B'} ,{'B','W','B','W','B','W','B','W'}};

	if (input_data[x][y] != map2[x-i][y-j])
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int i, j, x, y;
	int N, M;
	int ans=999;
	int cnt1 = 0, cnt2 = 0;
	
	cin >> N >> M;

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			cin >> input_data[i][j];
		}
	}

	for (j = 0; j <= M - 8; j++)
	{
		for (i = 0; i <= N - 8; i++)
		{
			for (x = i; x < i + 8; x++)
			{
				for (y = j; y < j + 8; y++)
				{
					cnt1 += black_check(x, y, i, j);
					cnt2 += white_check(x, y, i, j);
				}
			}
			ans = min(ans,min(cnt1, cnt2));
			cnt1 = 0;
			cnt2 = 0;
		}
	}
	
	cout << ans << endl;

	return 0;
}

개발환경 및  컴파일 기준  visual studio community 2017