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

---

0. 문제

 

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

1. 아이디어

 

1) N*M으로 주어진 체스판에서 8*8 크기의 체스판으로 잘라내려면 chess[0][0]부터 chess[N-6][M-6]의 범위만 검사하면 된다. (나머지는 범위가 겹침)

 

2) 가장 왼쪽 모서리에 있는 문자(시작하는 문자)가 'B'와 'W'일 경우를 나눠서 생각한다.

 

3) 시작하는 문자 또한 고정되는 값이 아니라 바뀔 수도 있으니 해당 경우의 수도 고려해서 최솟값을 리턴한다.

 

2. 소스코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
std::vector<std::string> chess;
int ReadChess(int i, int j) // i번째줄 j번째 문자부터 8*8 체스판 읽기
{
    int result = 0;
    char first = chess[i][j];
    if (first == 'B')
    {
        for (int p = 0; p < 8; p += 2) // 홀수번째줄
        {
            for (int m = 0; m < 8; m += 2) // 홀수번째 문자
                if (chess[i + p][j + m] != 'B') result++;
            for (int m = 1; m < 8; m += 2) // 짝수번째 문자
                if (chess[i + p][j + m] != 'W') result++;
        }
        for (int p = 1; p < 8; p += 2) // 짝수번째줄
        {
            for (int m = 0; m < 8; m += 2) // 홀수번째 문자
                if (chess[i + p][j + m] != 'W') result++;
            for (int m = 1; m < 8; m += 2) // 짝수번째 문자
                if (chess[i + p][j + m] != 'B') result++;
        }
    }
    else if (first == 'W')
    {
        for (int p = 0; p < 8; p += 2) // 홀수번째줄
        {
            for (int m = 0; m < 8; m += 2) // 홀수번째 문자
                if (chess[i + p][j + m] != 'W') result++;
            for (int m = 1; m < 8; m += 2) // 짝수번째 문자
                if (chess[i + p][j + m] != 'B') result++;
        }
        for (int p = 1; p < 8; p += 2) // 짝수번째줄
        {
            for (int m = 0; m < 8; m += 2) // 홀수번째 문자
                if (chess[i + p][j + m] != 'B') result++;
            for (int m = 1; m < 8; m += 2) // 짝수번째 문자
                if (chess[i + p][j + m] != 'W') result++;
        }
    }
    return std::min(result, 64 - result);
    //first가 바뀌었을 때가 최솟값일 가능성도 있으니 비교
    //(first가 바뀌면 result는 그냥 64-result가 된다.)
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int N, M, result = 64;
    std::cin >> N >> M;
 
    for (int i = 0; i < N; i++)
    {
        std::string line;
        std::cin >> line;
        chess.push_back(line);
    } // M개의 정사각형으로 이뤄진 string N개를 입력 받음
 
    for (int i = 0; i < N - 7; i++) // 0번째 줄부터
    {
        for (int j = 0; j < M - 7; j++) // i번째줄 0번째 문자부터
            result = std::min(result, ReadChess(i, j));
    }
    std::cout << result;
}

 

3. 결과

 

4. 피드백

 

• 문제에서 '체스판을 색칠하는 경우는 두 가지 뿐이다.'라는 문장에서 힌트를 얻었어야 한다.. 오래 걸렸다.

 

---