[BaekJoon] 1018 체스판 다시 칠하기 :: monton

문제

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

풀이

dfs를 이용

체스판이 8X8이므로 이 체스판의 첫번째 위치만 for문으로 dfs를 돌린다

첫번째가 B나 W로 시작하게 각각 돌려준다

간단한 dfs

코드

#include <iostream>
using namespace std;
 
int N, M,ans=10000000;
char arr[51][51];
 
void dfs(int n, int m,int x, int y, char cha,int cnt) {
    if (y == m) {
        y = m-8;
        x += 1;
        if (x == n) {
            ans = ans < cnt ? ans : cnt;
            return;
        }
    }
    else cha = cha == 'B' ? 'W' : 'B'; 
    if (arr[x][y] != cha) cnt++;
    
    dfs(n, m, x, y + 1, cha, cnt);
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    
    for (int i = 0; N - 8 >= i; i++) {
        for (int j = 0; M - 8 >= j; j++) {
            dfs(i + 8, j + 8, i, j, 'B', 0);
            dfs(i + 8, j + 8, i, j, 'W', 0);
        }
    }
    cout << ans;
}