[백준/C언어] 1018번 - 체스판 다시 칠하기

백준 웹사이트 "1018번 - 체스판 다시 칠하기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1018번: 체스판 다시 칠하기

---

소스 코드

#include <stdio.h>

int main(void){
    int N, M;
    scanf("%d %d", &N, &M);

// 1. 입력된 보드를 저장한다.
    char board[N][M];
    for(int i=0; i<N; i++){
        scanf("%s", &board[i]);
    }

// 2. 두 가지 모양의 체스판을 저장한다.
    char chessboard_B[8][8];
    char chessboard_W[8][8];
    int tag = 1; // 1 과 -1을 반복
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            if(tag==1){
                chessboard_B[i][j] = 'B';
                chessboard_W[i][j] = 'W';
            }
            else{
                chessboard_B[i][j] = 'W';
                chessboard_W[i][j] = 'B';
            }
            tag *= -1; // 1 -> -1 or -1 -> 1
        }
        tag *= -1;
    }

    /*
    printf("check chessboard\n");
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            printf("%c", chessboard_B[i][j]);
        }
        printf("\n");
    }
    */

// 3. 8x8 크기로 자르며, 칠해야 하는 개수의 최솟값을 구한다.
    int min=N*M;
    for(int i=0; i<N-7; i++){
        for(int j=0; j<M-7; j++){
            // (i, j)가 8x8의 가장 왼쪽 위인 경우
            // chessboard_B, chessboard_W 와 다른 개수
            int num_B=0, num_W=0;
            for(int k1=0; k1<8; k1++){
                for(int k2=0; k2<8; k2++){
                    if(chessboard_B[k1][k2] != board[i+k1][j+k2])
                        num_B++;
                    if(chessboard_W[k1][k2] != board[i+k1][j+k2])
                        num_W++;
                }
            }
            // min보다 작으면 min 업데이트
            if(num_B < min)
                min = num_B;
            if(num_W < min)
                min = num_W;
        }
    }
    printf("%d\n", min);
}

---

문제 풀이

  다음과 같이 세 단계로 나누어 코드를 작성합니다.

 

1. 입력된 보드를 저장합니다.

  N, M을 입력받으면 보드에 해당하는 이중배열 'board'를 N×M 크기로 선언합니다. 둘째 줄부터 입력되는 N개의 줄은 각각 string이므로, "%s"로 board[i]에 저장합니다. 이때 board[i]는 크기 M의 단일배열이겠죠? board[i][0]에 하나의 char, board[i][1]에 하나의 char... 등등 하나의 배열 요소에 하나의 char이 들어가게 됩니다. C언어에서 string의 마지막은 "\0"으로 표시되는데, board[i]의 크기를 크기 M으로만 지정하면 각 줄마다 있는 "\0"을 제외하고 char들을 저장할 수 있습니다.

 

2. 두 가지 모양의 체스판을 저장합니다.

  가능한 체스판은 두 가지가 있습니다: 왼쪽 위가 검은색인 경우(chessboard_B)와 왼쪽 위가 흰색인 경우(chessboard_W). 각각의 체스판에 해당하는 이중배열을 선언 및 초기화합니다. 이때 'tag'를 이용하여 깔끔하게 코드를 작성할 수 있는데, tag를 1로 초기화하면 -1을 곱할 때마다 1과 -1을 오갑니다. 체스판도 B와 W가 번갈아가며 나타나므로, 이를 응용해줍니다.

  Line 33 ~ 39는 두 체스판 chessboard_B, chessboard_W가 제대로 저장되었는지 확인하는 코드입니다.

 

3. 8×8 크기로 자르며, 칠해야 하는 개수의 최솟값을 구합니다.

  1단계에서 입력한 board가 8×8보다 크다면, 이를 8×8의 크기로 자른 경우들을 각각 확인해야 합니다. 예를 들어, 9×9의 보드가 주어진다면 나올 수 있는 8×8 보드는 네 가지입니다. 맨 왼쪽 위 칸이 board[0][0]인 보드, board[0][1]인 보드, board[1][0]인 보드, board[1][1]인 보드로 총 네 가지이겠죠? Line 44, 45의 for문을 통해 나올 수 있는 모든 8×8 보드들을 고려할 수 있으며, 이때 각 보드의 맨 왼쪽 위 칸은 (i, j)가 됩니다.

  하나의 8×8 보드를 잘라내면, 그 다음으로 할 것은 체스판과 비교하는 것입니다. 가능한 두 가지 체스판은 2단계에서 미리 chessboard_B와 chessboard_W로 만들어놓았죠? Line 48 ~ 56에서 8×8 보드와 각 체스판을 비교하여, 서로 다른 칸의 개수를 num_B와 num_W에 기록합니다.

  마지막으로 num_B와 num_W를 각각 min과 비교하여, min보다 작으면 새로운 min으로 대체합니다. 이렇게 하면 가능한 모든 8×8 보드의 num_B와 num_W를 비교하여 그들의 최솟값을 얻을 수 있습니다.