[백준] 1018번 체스판 그리기 - 결과 포함

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

1018번: 체스판 다시 칠하기

브루트 포스 문제는 모든 경우의 수를 시도하면서 결과를 구하는 것을 말한다.

모든 알고리즘 문제가 그렇지만 이 문제가 브루트 포스 알고리즘 문제라고 생각하면 쉽지만

만약에 사전에 주어진 것 없이 문제만 나왔다면 더 효율적인 방법이나 알고리즘을 찾으려고 괜히 더 생각했을 것 같다.

 

물론 더 좋은 방법이 있을 것이다.

내가 푼 방법은 모든 경우의 수를 시도해 보는 방법이다.

문제에서 준 힌트는 결국 체스판을 그리는 방법은 두 가지라는 것이다.

 

맨 왼쪽 위 즉 (0, 0)의 칸이 W (흰색)인 경우와, B (검은색)인 경우이다.

8 X 8 크기의 체스판을 어디서 어떻게 자르던지 결국 두 가지의 8X8 체스판 중에 가장 가까운 것을 선택해야 한다.

 

먼저 전체 체스판의 크기를 입력 받고 이를 문자열 배열로 저장한다.

이 체스판에서 8 X 8 크기의 정사각형이 나올 수 있는 모든 경우의 수를 시도한다.

위에서 말한 두 가지 경우의 체스판을 미리 정해놓고 여기에 대입하는 방법이다.

대입했을 때 색깔을 바꾸어야 하는 칸의 갯수를 구하고

마지막에 가장 최소인 갯수를 출력한다.

 

결과적으로 단순하고 쉽게 생각할 수 있는 방법으로 해결했지만 처음에는 무언가 더 효율적이고 좋은 방법이 없을까라는 의문때문에

쉽게 시작하지 못했다. 또한 중간에 문제가 있었는데 알고보니 애초에 미리 정해놓은 8X8 체스판을 잘못써놔서 답이 계속 이상하게 나왔었다. 앞으로 쉬운 부분은 더 완벽하게 정해놓는 연습을 해야겠다. 그리고 문제를 분리해서 단순하게 생각하는 능력도 길러야겠다.

 

 

[전체 소스 코드]

#include <iostream>
#include <vector>
using namespace std;

int whiteFirst(string str[8])
{
    int cnt = 0;
    string answer[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
    };
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if(answer[i][j] != str[i][j]){
                cnt++;
            }
        }
    }

    return cnt;
}

int blackFirst(string str[8])
{
    int cnt = 0;
    string answer[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
    };

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if(answer[i][j] != str[i][j]){
                cnt++;
            }
        }
    }

    return cnt;
}

int main()
{
    cin.tie(NULL);
    cin.sync_with_stdio(false);

    int M, N;
    int min = 64;

    vector<string> board;

    cin >> M >> N;
    for (int i = 0; i < M; i++)
    {
        string temp;
        cin >> temp;
        board.push_back(temp);
    }
    for (int i = 0; i <= M - 8; i++)
    {
        for (int j = 0; j <= N - 8; j++)
        {
            string board88[8];
            int rowIdx = 0;
            for (int k = i; k < i + 8; k++)
            {
                string row = board[k].substr(j, 8);
                board88[rowIdx] = row;
                rowIdx++;
            }
            
            int whiteFirstCount = whiteFirst(board88);
            int blackFirstCount = blackFirst(board88);
            if (whiteFirstCount < blackFirstCount)
            {
                min = whiteFirstCount < min ? whiteFirstCount : min;
            }
            else
            {
                min = blackFirstCount < min ? blackFirstCount : min;
            }
        }
    }

    cout << min << '\n';
}