[0629] 알고리즘

1018. 체스판 다시 칠하기

  그냥 브루트 포스 문제인데, 새삼 이런 알고리즘 문제는 발상을 잘 내야 한다는 것을 실감한 문제였다.

 

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
  std::cin.tie(NULL);

  int n, m, num, num1 = 0, num2 = 0, min;
  std::cin >> n >> m;
  min = n * m;
  char c;

  char chess[n][m];

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      std::cin >> c;
      chess[i][j] = c;
    }
  }
  
  for (int i = 0; i <= n - 8; i++)
  {
    for (int j = 0; j <= m - 8; j++)
    {      
      for (int k = i; k < i + 8; k++)
      {
        //처음 색을 B로
        for (int l = j; l < j + 8; l++)
        {
          if (k % 2 + l % 2 == 0 || k % 2 + l % 2 == 2)
          {
            if (chess[k][l] != 'B')
              num1++;
          }            
          else if (k % 2 + l % 2 == 1)
          {
            if (chess[k][l] != 'W')
              num1++;
          }
        }

		//처음 색을 W로
        for (int l = j; l < j + 8; l++)
        {
          if (k % 2 + l % 2 == 0 || k % 2 + l % 2 == 2)
          {
            if (chess[k][l] != 'W')
              num2++;
          }            
          else if (k % 2 + l % 2 == 1)
          {
            if (chess[k][l] != 'B')
              num2++;
          }
        }        
      }

      num = num1 < num2 ? num1 : num2;
      if (num < min) min = num;
      num1 = 0; num2 = 0;
    }
  }

  std::cout << min << '\n';

  return 0;
}

 

  문제에서 체스판의 크기를 8*8로 정해줬기 때문에 그 이상을 탐색할 필요가 없으므로 가장 바깥의 for문 2개는 주어진 체스판을 8*8 크기를 만족하는 범위에서 탐색하도록 했다. 여기까지는 괜찮았는데... 어떻게 체스판을 다시 칠할지를 탐색하는 거에서 편한 발상을 떠올리는게 어려웠었다.

 

  사실 가장 큰 힌트는... 문제에 있었다. 문제를 보면 중간에 이렇게 적혀있다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

  체스판을 칠하는 경우는 두 가지라고 문제에서 친절하게(...) 알려줬다. '맨 왼쪽 위칸의 색을 어떤 색으로 정의하는가'만 정해져있으면 그 다음엔 어느 색이 와야하는지 판별하는 과정은 간단하다. 체스판을 배열로 나타냈을 때, 해당 배열의 위치 인덱스를 통해 흰 칸인지 검은 칸인지 알아내면 되는 것이다... 그러니 구현할 때도 맨 왼쪽 위칸을 검은색으로 정했을 경우, 흰색으로 정했을 경우 두 가지로 나누어 다시 칠해야 하는 정사각형의 최소 개수를 세고 비교하여 최소값을 결정한다.

 

  저걸 알기 전까지는 그 전 칸의 색을 다른 변수에 기억하게 하여 비교하는 방법을 사용하려 했었는데, 이걸 보고는 너무나도 어이가 없도록 쉬워져서(ㅋㅋㅋㅋㅋ) 깜짝 놀랐다...

 

* 오늘의 교훈 : 문제를 잘 읽자! 규칙을 잘 찾아보자!