[백준 1018번/C언어] 체스판 다시 칠하기 브루트포스로 풀이

백준 1018번 문제를 브루트포스 알고리즘으로 풀어보았습니다. 

백준 1018번: https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

문제 내용은 아래와 같습니다. 예제 입출력은 7개가 준비되어 있으니, 접속하여 확인하기 바랍니다. 여기서는 최소한의 문제 이해를 위한 첫 번째 예제만 두었습니다. 

 

 

우선 해당 문제를 풀기 위한 브루트포스(brute force) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 걸맞게 무식하게 하나하나 모든 경우의 수를 체크해 보는 알고리즘을 뜻합니다. 결국 해당 문제는 존재하는 모든 경우의 수를 체크하여 결괏값을 도출해내야 하기 때문에 모든 경우의 수를 반복하는 과정에서 불필요한 과정을 최소화하는 것이 핵심이라고 볼 수 있습니다. 즉, loop 안에서 불필요한 과정을 최대한 삭제하고 꼭 필요한 과정만을 담아, 반복횟수를 최소화하고, 속도를 높여야 하는 것이 주요 과제라고 볼 수 있습니다. 

 

이를 반영하여 코드를 아래와 같이 구성해보았습니다. 전반적인 알고리즘은 8x8크기로 자른 보드판에 칠하는 횟수를 세는 countSquare() 함수를 모든 8x8크기로 자를 수 있는 경우에 수에 사용하여 그중 최솟값을 찾는 방식입니다. 

보드판에 칠하는 횟수를 count할 때는 

1. 가장 왼쪽 위칸이 흰색인 경우
2. 가장 왼쪽 위칸이 검정색인 경우

 

두 가지를 모두 체크하기 위해 두 개의 변수를 만들어서 기록합니다. x좌표와 y좌표 모두가 짝수/홀수일 때는 가장 왼쪽 위칸의 색과 같도록 해야 하고, 하나가 짝수 하나가 홀수일 때는 가장 왼쪽 위칸의 색과 다르게 해야 합니다. countSquare() 함수는 둘 중 더 작은 수를 return하게 되고, main 함수에서 이들 중 가장 작은 값을 찾아서 출력하게 됩니다. 

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 각 경우에 칠하는 횟수를 구할 함수 (초기 x, y값과 보드를 인자로 받는다)
int countSquare(int startX, int startY, char **board);

int main() {
	// 보드 크기 입력 받기 (XxY 크기의 보드)
    int X, Y;	
    scanf("%d %d", &X, &Y);
    
    // 보드 2차원 배열로 입력받기
    char **board = (char **)malloc(sizeof(char*) * X);
    char c;
    for (int x = 0; x < X; x++) {
        board[x] = (char *)malloc(sizeof(char) * Y);
        for (int y = 0; y < Y; y++) {
            do {
                c = getchar();
            } while (!isalpha(c));
            board[x][y] = c;
        }
    }
    
    
    // 출력값 찾기
    int res = 64;  // 8x8 체스판에서 생길 수 있는 횟수 최대값(64)를 초기값으로 설정
    int temp;  // 임시로 해당 경우에서 칠한 횟수를 담아놓을 변수
    for (int x = 0; x <= (X - 8); x++) {
        for (int y = 0; y <= (Y - 8); y++) {
            temp = countSquare(x, y, board);
            if (temp < res) res = temp;
        }
    }
    
    printf("%d", res);
    free(board);
}

int countSquare(int startX, int startY, char **board) {
    int countW = 0, countB = 0;	 // (startX, startY) 좌표를 'W'로 시작할지 'B'로 시작할지에 따라 count하는 두 개의 변수
    for (int x = startX; x < (startX + 8); x++) {
        for (int y = startY; y < (startY + 8); y++) {
        	// x와 y 모두 짝수이거나 홀수일 경우 (startX, startY) 좌표값과 같아야 하고
            // x와 y 중 하나가 짝수, 하나가 홀수일 경우 달라야 함
            if (((x % 2) == (y % 2))) {	
                if (board[x][y] == 'W') countB++;
                else countW++;
            } else {	
                if (board[x][y] == 'B') countB++;
                else countW++;
            }
        }
    }
    
    // 둘 중 작은 값을 return
    if (countB < countW) return countB;
    else return countW;
}

 

 

 

 

이렇게 푼 결과는 아래와 같이 정답으로 확인할 수 있습니다.