[백준 / BOJ] C++ 1018 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

 

문제

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

1018번: 체스판 다시 칠하기

 

풀이

입력받은 체스판을 8×8 사이즈로 잘라 올바르게 되기 위해 색칠해야할 가장 적은 횟수를 출력하는 문제. 브루트포스(Brute Force) 문제로 가능한 모든 경우의 수를 계산해본 후 가장 작은 값을 출력하면 된다. 체크할 경우는 흰색으로 시작하는 경우와 검은색으로 시작하는 두가지 밖에 없다. 따라서 이 보드들을 string 배열로 만들어놓으면 된다.

결국 입력받은 배열에서 일부분을 위에서 만든 배열과 비교하며 다른 부분의 개수를 구하면 된다. 여기서 중요한 점은 흰색으로 시작하는 경우와 검은색으로 시작하는 경우를 모두 고려해야 한다. 간혹 첫 번째 칸의 색을 바꾸면 최솟값이 되는 경우가 존재하기 때문.

따라서 흰색으로 시작하는 배열과 비교하는 경우와 검은색으로 시작하는 배열과 비교하는 경우를 각각 wbCnt, bwCnt 함수로 구현했다. for문으로 가능한 모든 경우에 대해 두 함수의 return 값 중 작은 값을 찾아간다. 최종적으로 가장 작았던 값을 출력하면 문제를 해결할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

string WB[8] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
};

string BW[8] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
};

string B[50];

int wbCnt(int x, int y) {
  int cnt = 0;
  for (int i = 0; i < 8; i++)
    for (int j = 0; j < 8; j++)
      if (B[x + i][y + j] != WB[i][j])
        cnt++;
  return cnt;
}

int bwCnt(int x, int y) {
  int cnt = 0;
  for (int i = 0; i < 8; i++)
    for (int j = 0; j < 8; j++)
      if (B[x + i][y + j] != BW[i][j])
        cnt++;
  return cnt;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int x, y, m = 98765;
  cin >> x >> y;
  for (int i = 0; i < x; i++)
    cin >> B[i];
  for (int i = 0; i + 8 <= x; i++) {
    for (int j = 0; j + 8 <= y; j++) {
      int temp = min(wbCnt(i, j), bwCnt(i, j));
      if (temp < m)
        m = temp;
    }
  }
  cout << m;
  return 0;
}