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

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

완전탐색으로 8 X 8 로 떼어낼 수 있는 부분을 전부 떼어내서

바꾸는 횟수를 전부 다 구했습니다

 

주의할점은 왼쪽 위가 W로 시작했더라도 

1) 왼쪽 위가 그대로 W인 체로 바꿔지는 칸의 숫자 세기

2) 왼쪽 위를 B로 바꾼 후 바꿔지는 칸의 숫자 세기

 

이렇게 접근을 해야되는점이었습니다.

 

처음에 진짜 무식한 방법으로 완전탐색을 돌리니 시간초과가 나와서 다른 분의 풀이를 참고했습니다.

 

풀이를 보니 각 칸의 인덱스를 i , j 로 정의할 때 

i+j 가 짝수일경우와  i+j 가 홀수일때 서로 다른 색이 칠해져야 된다는 풀이법을 봤는데

솔직히 더 깔끔한 것 같습니다

 

하지만 저는 저 풀이를 구현할 능력이 아직 없으므로,,, 좀 원시적인 방법을 사용했습니다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
vector<string> one(50);
 
//흰색이 왼쪽 맨 위인 배열
char whitefirst[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'
};
 
//검정색이 왼쪽 맨 위인 배열
char blackfirst[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'
};
//왼쪽 위가 흰색이라고 가정하고 숫자 셈
int white(int x, int y) {
    int result = 0;
 
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++) {
            //왼쪽 위가 흰색이라 가정하기 때문에 whitefirst 배열과 비교
            if (one[x + i][y + j] != whitefirst[i][j])
                result++;
        }
    return result;
}
//왼쪽 위가 검정이라고 가정하고 숫자 셈
int black(int x, int y) {
    int result = 0;
 
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++) {
            if (one[x + i][y + j] != blackfirst[i][j])
                result++;
        }
    return result;
}
 
int main() {
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
        cin >> one[i];
    //최소값 계산을 위해 답이 될 수 없는 아무 큰값이나 설정
    int answer = 100000000;
 
    for(int i=0 ; i<=n-8 ; i++)
        for (int j = 0; j <= m - 8; j++) {
            //최소값 도출
            answer = min(answer, min(black(i, j), white(i, j)));
        }
 
    cout << answer;
    
    return 0;
}