c++) 백준 1018 - 체스판 다시 칠하기

완전탐색을 이용해서 풀 수 있는 문제입니다.

 

• 접근방법

1. board가 주어졌을 때 8x8 크기의 체스판으로 자르는 모든 경우의 수를 생각해야 합니다.

 

2. 각 경우의 수에 대해 생각해보면, x좌표 + y좌표 값이 짝수일 경우 / 홀수일 경우로 나누어서 생각할 수 있습니다.

x+y 값이 짝수면 흰색, x+y값이 홀수면 검은색 인 것을 알 수 있습니다.

( 가장 왼쪽 위 첫 블록이 검은색이면 반대가 됩니다. )

따라서 cnt1 에는 첫 블록이 흰색일 때 바꿔야 하는 블록의 개수

cnt2 에는 첫 블록이 검은색일때 바꿔야 하는 블록의 개수

를 따로 저장해서 최소값을 구해주었습니다.

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define INF 98765432
using namespace std;
int N,M;

int counting(vector < vector <int> > &board, int y, int x) {
    int cnt1=0,cnt2=0;
    for(int i=y; i<y+8; i++) {
        for(int j=x; j<x+8; j++) {
            // x,y 좌표 더한값이 짝수인 경우
            if((i+j) % 2 == 0) {
                // cnt1 : 첫 블록이 white인 경우의 바꿔야 하는 블록의 개수
                // cnt2 : 첫 블록이 black인 경우의 바꿔야 하는 블록의 개수
                if(board[i][j] == 1) cnt1++;
                else cnt2++;
            }
            else {
                if(board[i][j] == 0) cnt1++;
                else cnt2++;
            }
        }
    }
    int result = INF;
    result = min(result, cnt1);
    result = min(result, cnt2);
    return result;
}

int solution(vector < vector <int> > &board) {
    int result = INF;
    // 움직일 수 있는 경우의수
    for(int i=0; i<=N-8; i++) {
        for(int j=0; j<=M-8; j++) {
            int cnt = counting(board,i,j);
            result = min(cnt,result);
        }
    }
    return result;
}

int main()
{
    scanf("%d %d",&N,&M);
    vector < vector <int> > board(N, vector<int>(M,0));
    string s;
    for(int i=0; i<N; i++) {
        cin >> s;
        for(int j=0; j<M; j++) {
            if(s[j] == 'B') board[i][j] = 1;
        }
    }
    int result = solution(board);
    printf("%d\n",result);
}