1018번 - 체스판 다시 칠하기

---

문제 링크

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 88 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 88 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

---

예제

입력

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력

1

---

풀이

이 문제는 전체 N x M 크기의 정사각형으로 이루어져있는 보드를 8x8 크기로 잘라 체스판을 만드는 것이다.

1. char형 배열안에 입력을 받아 넣는다. 가로 세로의 크기는 50보다 작거나 같은 2차원 배열이다.
2. 각 행과 열을 순차적으로 돌아야한다. 8 x 8 칸만 따로 자르는 것이기 때문에 배열의 시작 좌표가 (x, y)라고 한다면(x, y)부터 (x + 8, y + 8) 까지 확인한다.
3. 체스 판이기에 검정색과 하얀색이 규칙적으로 나오는지 확인해야한다.
4. 모서리가 하얀색일때와 검정색일때 두 가지를 검사하여 둘 중 가장 작은수를 리턴한다.
5. 2번과 4번을 반복하며 반복할때 마다 x와 y의 값을 증가시키며 확인한다. 순환하는 값은 (N - 8 + 1, M - 8 + 1) 만큼 순환한다.

최대 연산 계산

N과 M이 최대로 가질 수 있는 수는 50이다.
한 블럭(8x8)을 연산하면 64번을 연산한다.
그것을 흰색과 검정색 2번 연산한다.
N과 M은 최대 42번을 순환하므로 42^2 x 64 x 2가 된다.
즉, 시간복잡도는 O(N^2)이다.

코드

#include <iostream>
#include <math.h>

using namespace std;

char blocks[51][51];

int RedrawBlockCount(int startX, int startY){
    int black_redrawCount = 0, white_redrawCount = 0;

    // 0,0이 검정일때    
    for (int y = 0; y < 8; y++){
        for (int x = 0; x < 8; x++){
            if (y % 2 == 0){
                if (x % 2 == 0 && blocks[startY + y][startX + x] != 'B') 
                    black_redrawCount++;
                if (x % 2 == 1 && blocks[startY + y][startX + x] != 'W') 
                    black_redrawCount++;
            }
            else{
                if (x % 2 == 1 && blocks[startY + y][startX + x] != 'B') 
                    black_redrawCount++;
                if (x % 2 == 0 && blocks[startY + y][startX + x] != 'W') 
                    black_redrawCount++;
            }
        }
    }

    for (int y = 0; y < 8; y++){
        for (int x = 0; x < 8; x++){
            if (y % 2 == 0){
                if (x % 2 == 0 && blocks[startY + y][startX + x] != 'W') 
                    white_redrawCount++;
                if (x % 2 == 1 && blocks[startY + y][startX + x] != 'B') 
                    white_redrawCount++;
            }
            else{
                if (x % 2 == 1 && blocks[startY + y][startX + x] != 'W') 
                    white_redrawCount++;
                if (x % 2 == 0 && blocks[startY + y][startX + x] != 'B') 
                    white_redrawCount++;
            }
        }
    }

    return min(black_redrawCount, white_redrawCount);
}

int main(){
    int N, M;
    int min = 9999999;
    int drawCount;

    cin >> N >> M;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> blocks[i][j];

    int cul = N - 8 + 1;
    int row = M - 8 + 1;

    for (int y = 0; y < cul; y++){
        for (int x = 0; x < row; x++){
            drawCount = RedrawBlockCount(x, y);
            if (drawCount < min) min = drawCount;
        }
    }

    cout << min << endl;

    return 0;
}

결과

0ms, 다른 풀이로 나중에 다시 시도해봐야겠다. 좀더 좋은 풀이가 있을 것 같음.