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

Sol)

#include <stdio.h>

int main()
{
    int row, col;
    int min = 64;
    char input_board[50][51]; //문자열로 입력받을 것이기 때문에 NULL문자 자리까지 51자리.

    scanf("%d %d", &row, &col);

    for(int j = 0; j < row; j++) {
        scanf("%s", input_board[j]); // \n, 즉 개행문자를 처리할 수 있는 가장 간단한 방법은 %s 서식지정자로 입력받는 것이다.
    }

    for(int k = 0; k < row - 7; k++) { //검사할 8 * 8 보드판을 세로 방향으로 이동시킬 for 문. 세로 길이가 8이 나와야 하기때문에 row - 8까지만 이동
        for(int i = 0; i < col - 7; i++) { //검사할 8 * 8 보드판을 가로 방향으로 이동시킬 for 문. 가로 길이가 8이 나와야 하기때문에 col - 8까지만 이동
            int cnt = 0;
            for (int k_board = k; k_board < k + 8; k_board++) { //k_board는 8*8 체스판에서 행의 index
                for (int i_board = i; i_board < i + 8; i_board++) { //i_board는 8*8 체스판에서 열의 index
                    cnt += (i_board + k_board) % 2 == 0 ^ input_board[k_board][i_board] == 'B'; // ^ -> XOR 연산자
                }
            }
            cnt = cnt > 64 - cnt ? 64 - cnt : cnt; //64 - cnt 는 반전됐을 때의 카운트 수. 
            min = min > cnt ? cnt : min;
        }
    }

    printf("%d\n", min);
    return 0;
}

 

이 문제는 보드판을 입력받을 때 주의점이 있다.

만일 scanf의 서식지정자를 %c로 받을 경우, 각 행을 입력하고 엔터를 칠 때 버퍼에 입력되는 개행문자(\n)들이 다음 행의 첫번째 인덱스에 들어오게 된다. 따라서, 문자열을 제외한 공백문자를 무시하는 %s를 이용해 입력받는 것이 가장 효율적인 방법이다. 일일이 getchar()와 같은 함수로 처리하기는 너무 비효율적이다. 이 문제에서 2차원 char배열의 입력을 %s로 처리할 수 있는 이유는, C언어에서 문자열은 char*나 char[]형으로 저장하기 때문이다. 2차원 배열은 1차원 배열들의 집합이라고 생각할 수 있으므로, 2차원 배열들의 세로 인덱스, 즉 '행'에 해당하는 인덱스를 각각의 문자열(or 한 줄짜리 입력), 즉 1차원 char배열을 가리키는 포인터라고 생각하면 된다. 따라서 입력받을 때 세로 인덱스만 사용하는 것이다.

 

그 후, 8*8보다 큰 보드 판이 들어왔을 경우, 8*8 짜리 스코프를 이동시켜줘야 하기 때문에 nested for문을 사용했다.

배열의 규칙 기준은 가장 왼쪽 위 글자가 'B' 냐 'W' 냐로 나뉜다. 8*8 체스판중 'B'로 시작하는 체스판을 기준으로 잡으면, 행 인덱스 + 열 인덱스 % 2 의 값이 0일 때 'B'가 나오고, 1일 때 'W' 가 나오게 된다. 여기서는 ^(XOR)연산자를 사용했다. 어차피 == 연산자의 값이 true or false, C언어에서는 1 or 0으로 리턴되므로 비트연산자를 사용할 수 있다. XOR연산자는 두 비교 대상이 다르면 1, 같으면 0을 리턴하므로, 행 인덱스 + 열 인덱스 % 2 의 값이 0임에도 B가 아니면 각각 1, 0을 리턴해 값이 다르므로 count에 1을 더해주고, 0인데 B면 둘 다 1을 리턴해 아무것도 더해주지 않는 식으로 카운트를 해 나간다.

 

가장 왼쪽 위 글자가 'B'인 경우를 카운트 했으니 이제 'W'일 경우를 카운트 해야 한다. 이는 잘 생각해 보면 for문을 다시 돌리지 않고도 구할 수 있다. 가장 왼쪽 위 글자가 'W'인 경우는 위에서 구한 가장 왼쪽 위 글자가 'B'인 8*8 배열을 전부 다 반전시켜서 구할 수 있다. 따라서 8*8배열의 64칸에서 'B'일 때 바꿔야 했던 cnt를 빼주기만 하면 'W'일 때의 cnt를 구할 수 있게 된다. 

예를 들면, 'B'일 때는 [0][0] 이 B, [0][1] 이 W여야 했기에 만일 (0,0)에 W가 있다면 이를 바꾸고 cnt를 올려야 했다. 하지만 'W' 배열의 경우, [0][0]이 W일 때 바꾸지 않고, [0][1]이 W면 바꾼다. 즉, 바꿔야 하는 좌표가 완전히 반대가 되므로 둘 중 하나만 카운트 해도 나머지는 자동으로 64에서 빼 구할 수 있는 것이다.

 

우리가 가장 왼쪽 위가 'B'인 경우는 행 인덱스 + 열 인덱스 % 2 의 값이 0일 때 'B'라고 했다. 그렇다면 8*8스코프를 옮기기 위해 k와 i의 값이 0에서 바뀌면 어떻게 될까? 예를 들어 i가 1이 될 경우 시작 인덱스, 즉 가장 왼쪽 위 인덱스가 [0][1]이 돼 버린다. 이러면 행 인덱스 + 열 인덱스 % 2 의 값이 1일때 'B'가 된다. 하지만 그렇다 하더라도 위 식에는 아무런 문제도 생기지 않는다.

예를 들어, [0][1]일 때 ^ 왼쪽 항의 값은 0, [0][1]이 'B'이면 오른쪽 항의 값은 1이 되어 카운트가 올라가게 된다. 이것은 단순히 첫번째 탐색 기준이 가장 왼쪽 위가 'B'일 때에서 'W'일 때로 바뀐 것 뿐이다. 우리가 구해야 하는 값은 왼쪽 위 기준값이 'B'이든 'W'이든 주어진 체스판을 가장 최소한으로 바꾸는 횟수이기때문에 i,k값의 변화에 따라 탐색 기준이 변화하는 것은 신경쓰지 않아도 된다.

 

 

 

8*8짜리 정답 체스판을 만들어 하나하나 비교하는 방법이나, 인접한 체스판의 문자가 같은지 다른지를 확인하는 풀이또한 가능하나, 위 풀이가 가장 효율적이고 깔끔한 풀이라고 생각한다.

 

 

지금 내 수준에서는 쉽지 않은 문제였다.

풀이는 다음 블로그의 풀이를 참고했다.

https://terry1213.github.io/backjoon/1018/