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

문제 이해

- M * N 크기의 보드가 주어진다.

- 보드는 검은색 또는 흰색으로 칠해져있다.

- 이 보드로 체스판을 만들 예정인데 8 * 8 크기이고, 검은색과 흰색이 번갈아 칠해져야 한다.

- 체스판은 그러므로 맨 왼쪽 위칸이 흰색인 경우와 검은색인 경우 두 가지만 존재한다.

- 8 * 8 크기로 자른 뒤, 다시 칠해야 하는 정사각형의 최소 개수를 구하라.

 

<입력>

- N, M; 보드의 크기 (8 ~ 50)

- B: Black

- W: White

 

<출력>

- 8*8로 자른 뒤 다시 칠해야하는 정사각형 개수의 최솟값

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 128MB

 

 

문제 풀이

브루트포스 혹은 분할정복을 써야한다고 생각했는데

보드의 크기가 작아 브루트포스로도 충분히 풀 수 있다고 생각했다.

 

 

처음에는 8*8로 자른 뒤, 처음 시작이 W인것과 B인것으로 하여

현재 블록과 다음 블록을 비교하는 식으로 칠해야하는 개수의 최솟값을 구하려고 했다.

 

분명 위의 방법도 구현하는 방법이 있겠지만 구현에 애를 먹었고,

인터넷의 풀이를 참조한결과 처음부터 체스판 두 개를 선언해둔 뒤, 비교하는 방식을 찾을 수 있었다.

구현 방식도 훨씬 간단했다.

char WB[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 BW[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'
};

 

 

현재 블록과 다음 블록을 비교하는 방식에서

가능한 체스판의 경우의 수로 비교하는 방식으로 넘어가며, for문 조건문의 수정이 필요했는데

캐치하는데 조금 시간이 걸렸다.

for(int k = i; k < i+8; k++){
    for(int l = j; l < j+8; l++){
        if(map[k][l] != WB[k][l]){
            tmpAns1++;
        }if(map[k][l] != BW[k][l]){
            tmpAns2++;
        }
    }
}

 

위의 코드의 문제가 보이는가?

 

바로 i와 j가 0일경우 잘 작동하지만,

만약 1이상이되면 WB와 BW배열에서 잘못된 인덱스에 접근하게 된다.

 

 

이런 사소한 반복문에서의 실수를 주의하도록 하자.

아래는 제대로 고친 코드이다.

for(int k = 0; k < 8; k++){
    for(int l = 0; l < 8; l++){
        if(map[i + k][j + l] != WB[k][l]){
            tmpAns1++;
        }if(map[i + k][j + l] != BW[k][l]){
            tmpAns2++;
        }
    }
}

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

char map[55][55];
char WB[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 BW[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 main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin>>map[i][j];
        }
    }

    int ans = 987654321;
    for(int i = 0; i <= n-8; i++){
        for(int j = 0; j <= m-8; j++){
            int tmpAns1 = 0, tmpAns2 = 0;

            for(int k = 0; k < 8; k++){
                for(int l = 0; l < 8; l++){
                    if(map[i + k][j + l] != WB[k][l]){
                        tmpAns1++;
                    }if(map[i + k][j + l] != BW[k][l]){
                        tmpAns2++;
                    }
                }
            }

            tmpAns1 = min(tmpAns1, tmpAns2);
            ans = min(tmpAns1, ans);
        }
    }

    cout<<ans;
    return 0;
}

비교해야 할 배열의 경우의 수가 적다면,

꼭 주어진 배열 안에서 비교할 필요가 없이 미리 선언한 뒤 비교하는 방식도 있다는 걸 배울 수 있었다!