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

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

1018번: 체스판 다시 칠하기

 

문제 분석: 

주어지는 n*m 의 배열이 있다. 이 배열은 각 칸이 B혹은 W로 칠해져있다.

이 배열에서 나올 수 있는 8*8 배열 중에, 가장 적은 칸을 칠해서 (W이면 B로, B이면 W로) 바둑판 모양을 만든다.

바둑판을 만들 수 있는 가장 작은 색칠 횟수를 구해라.

 

구현한 코드: 

// 백준 #1018
#include <stdio.h>

char arr[50][50];
int n, m;
int min_cnt = 1000;

void check(int a, int b) {

    int i, j;
    
    // 좌표 (a, b) 당 두 번의 확인이 필요하다. 
    char wb = 'B';	// (1) 첫 칸을 BLACK으로 칠한다고 가정하고 돌려본다. 
    for(int k = 0; k<2; k++){
        int cnt = 0;

        for (i = a; i < a+8; i++) {
            for (j = b; j < b+8; j++) {
                if (arr[i][j] != wb)
                {
                    cnt++;
                }
                if (wb == 'B') wb = 'W';
                else wb = 'B';
            }
            if (wb == 'B') wb = 'W';
            else wb = 'B';
        }

        if (cnt < min_cnt) {
            min_cnt = cnt;
        }
        wb = 'W'; // (2) 첫 칸을 WHITE로 지정하고 다시 돌려본다. 
    }
}

int main(void) {
    
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", &arr[i]);
    }

    for (int i = 0; i < n-8+1; i++) {
        
        for (int j = 0; j < m-8+1; j++) {
            check(i, j);
        }
    }

    printf("%d", min_cnt);

 

1. check()함수에 파라미터로 8*8 바둑판의 맨 왼쪽 위 좌표를 준 후에, 거기서부터 8*8의 색을 비교한다. 

 

2. wb에 처음에 'B'를 넣어서 하나하나 비교하고 색칠 횟수를 계산한다.

그 다음에는 (0, 0) 이 'W'인 경우부터 하나하나 비교하고 색칠 횟수를 계산한다.

 

3. 만약 cnt 가 min_cnt 보다 작으면 min_cnt를 업데이트 해준다.