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

문제

백준 1018 문제 보기

접근 방법

각 (0, 0)부터 (N - 7, M - 7)까지 8 * 8의 죄판을 그릴 수 있다. 각 점을 돌면서 B, W를 한번씩 수행하고 정답을 출력한다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int N, M;
int map[51][51];
int map_copied[51][51];
int check[51][51];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int sr, sc;
int cnt, ans = 987654321;

void brute(int r, int c, int num) {
    // 현재 좌표가 가져야할 색이 아니면
    if(map_copied[r][c] != num) {
        // 색을 바꾸고
        map_copied[r][c] = num;
        // 카운트 증가
        cnt ++;
    }

    // 방문 체크
    check[r][c] = 1;

    // 4방향 검사
    for(int i = 0; i < 4; i ++) {
        int nextR = r + dr[i];
        int nextC = c + dc[i];

        if(nextR >= sr && nextC >= sc && nextC < sc + 8 && nextR < sr + 8){
            if(!check[nextR][nextC]) {
                // 다음 색은 현재 색과 무조건 대치
                brute(nextR, nextC, -num);
            }
        }
    }
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < M; j ++) {
            char temp;
            scanf(" %c", &temp);

            if(temp == 'W') {
                // 흰색이라면 1 저장
                map[i][j] = 1;
            } else {
                // 검정이라면 -1 저장
                map[i][j] = -1;
            }
        }
    }

    // 8 * 8 모든 범위 계산
    for(int i = 0; i < N - 7; i ++) {
        for(int j = 0; j < M - 7; j ++) {
            // map 복사
            memcpy(map_copied, map, sizeof(map));
            // 방문 여부 초기화
            memset(check, 0, sizeof(check));
            // 시작 위치 저장, 카운트 초기화
            sr = i, sc = j, cnt = 0;
            // 검정색부터 완전 탐색 시작
            brute(i, j, -1);
            // 최소 저장
            ans = min(ans, cnt);

            memcpy(map_copied, map, sizeof(map));
            memset(check, 0, sizeof(check));
            cnt = 0;
            brute(i, j, 1);
            ans = min(ans, cnt);
        }
    }

    cout << ans;
    return 0;
}