[BaekJoon 1018][⚪3] 체스판 다시 칠하기

❓ 문제

백준 1018 - “체스판 다시 칠하기”

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (브루트 포스)

- 알고리즘

• Brute Force

- 설명

브루트 포스 방식으로 가능한 모든 경우의 수를 탐색하면서 결과값을 도출하는 방식이다.

'8 <= N, M <= 50'이라는 좁은 구간과 '2초'라는 널널한 시간 제한이 있는 것을 보고, 브루트 포스로 해도 충분하다는 생각이 들어서 바로 구현했다. 다른 더 좋은 방법이 있을까도 생각했지만, 지금 당장은 생각나는 것이 없기도 하고 대부분의 사람들이 비슷한 방식으로 푼 것으로 보아 정석인 것 같다.

8 x 8 크기의 배열을 순회하는 작업은 상수 시간으로 두고, N, M의 루프가 중요하므로 전체적인 시간 복잡도는 O(N·M)이라고 볼 수 있다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iM{};
    cin >> iN >> iM;

    vector<string> vecBoard(iN);
    for(int i = 0; i < iN; ++i)
    {
        cin >> vecBoard[i];
    }

    int iMin{ 64 }; // 최대로 나올 수 있는 값은 64이므로
    for(int i = 0; i <= iN - 8; ++i)    // 왼쪽 시작점은 0 ~ (iN - 8)까지
    {
        for(int j = 0; j <= static_cast<int>(vecBoard[i].size() - 8); ++j) // 위쪽 시작점은 0 ~ (vecBoard[i].size() - 8)까지
        {
            char chCurr{ 'B' }; // 현재 예상되는 문자
            int iBlack{}, iWhite{}; // 각각의 색상이 다시 칠해져야하는 횟수

            // 8 * 8 크기의 배열을 순회
            for(int iRow = i; iRow < i + 8; ++iRow)
            {
                for(int iCol = j; iCol < j + 8; ++iCol)
                {
                    // 예상되는 문자와 같은지를 검사해서 각각의 횟수를 늘림
                    vecBoard[iRow][iCol] == chCurr ? ++iWhite : ++iBlack;

                    // 다음 칸 가기전에 예상되는 문자 바꿈
                    chCurr = chCurr == 'B' ? 'W' : 'B';
                }

                // 다음 열 가기전에 예상되는 문자 다시 바꿈
                chCurr = chCurr == 'B' ? 'W' : 'B';
            }

            iMin = min(iMin, min(iBlack, iWhite));
        }
    }

    cout << iMin;

    return 0;
}

---

💭 후기

이번 문제는 조건과 제한이 널널해서 브루트 포스로 충분히 풀렸지만, 여기서 더 조건이 빡빡해지거나 변형이 있으면 다른 알고리즘을 써야할지도 모른다는 생각이 들었다. 그건 앞으로 여러 문제를 풀면서 몸으로 체득하는 수 밖에 없겠지..?

🔗 참고자료

• 브루트 포스 알고리즘