백준 1018번 <체스판 다시 칠하기> - C++

처참한 결과 그 자체가 아니지 않을 수 없지 않는가

solved.ac class2에 있는 문제다. 실버로 들어왔다고 쫄아가지고 엄청 오래 걸렸다. 처음 생각의 과정부터 찬찬히 한 번 살펴보자

문제 분석

CNN의 컨볼루션 필터랑 똑같은 개념이다

n*m칸 짜리 B와 W로 이루어진 나무판이 주어지면, 8*8짜리 필터로 나무판을 한 칸씩 돌면서, 어떤 부분에 위치했을 때 체스판으로 만들 기 위해 칠할 수 있는 칸의 개수가 가장 적은가? 이다

가로와 세로 : M, N 색배열이 주어짐 8*8크기의 체크판으로 만들어야 함 근데 이 보드가 체스판 배열이 아닐 수도 있기에, 8*8로 자르고 몇 개는 다시 칠함 8*8을 골라내는 건 아무 데나 상관 없음 칠해야 하는 정사각형의 최소개수를 구해야함

문제 분석을 이렇게 메모해 두고 시작했땨

 

멍청했던 사고의 과정

===================================================================  1. 현재의 체스판(옮겨다니는 8*8)에 있는 w개수와 b개수를 저장함  2. b개수와 w개수의 절댓값 차이를 구해서 mini에 저장 b, w값도 저장  3. for하면서, mini, b, w값을 업데이트  4. mini를 만들어낸 b,w가 각각 32가 되어야 하므로, 작은 값을 32에서 빼줌!  5. 개수로 세면 안 됨. BBBBWWWW면 4개 4개로 세어지잖아...  6. WB, BW가 연속되면 cnt++하는 걸로 세긴 했음 일단(1시간째)  7. 최소로 칠할 수 있는 cnt를 구할 때 k, l을 저장해서,  B, W로 시작하는 각각의 8*8체스판을 저장. mini 값을 가진 i, j를 불러와서, 8개8개 다시 반복  B or W 체스판과 비교하며 다른 개수를 카운트함 ===================================================================

 

색깔별로 시간대별 사고의 흐름이다

처음엔 간단하구나 생각했다 판을 옮겨다니면서, 총 64개의 b(black), w(white) 개수를 센다. 각각이 32에 가까울 수록 색을 바꾸어 줄 칸이 적어진다는 의미니까

그래서 두 수의 절댓값 차이(색을 칠할 칸의 수) 와 b,w를 업데이트하며, 차이가 최소일때의 b,w 개수를 맞추어야 하기에 32에서 b,w중 작은 수를 빼면 내가 칠해야 할 칸 수다!

이렇게 되면 순조롭다. 사실 사고 과정에서 틀린 건 없다. 다만 고려하지 않았던 점은, 색깔이 연속해서 나타나는 경우이다..

BWBWBWBW일 때 b : 4, w : 4

BBBBWWWW일 때 b : 4, w : 4

하하

다음 아이디어

 

WB or BW가 연속해서 나타나면 cnt를 1씩 증가시켜 준다.

필터가 나무판을 돌면서 이 cnt값이 가장 높은 부분이 칠할 개수가 가장 적은 부분일 것이다.

그때의 필터의 시작 인덱스를 찾아서, B인지 W인지 파악한다. 알파벳에 따라 만들어둔 B체스판, W체스판과 비교하며 일치하지 않는 것의 개수를 센다.

 

체스판은 이딴식으로 노가다로 만들었다.

 

여기에서도 심각한 결점이 있다.

 

시작 인덱스가 B라고 해서, W라고 해서, 무조건 그 체스판을 B, W 체스판으로 대조해서는 안 된다. 경우에 따라 B로 시작하지만 W체스판이, W로 시작하지만 B 체스판이 더 효율적일 때가 있다. 평소에는 효율을 그렇게 좋아하면서 이건 왜 안 따짐 심지어 최솟값 구하는데???

 

여기서 수정하려면 할 수 있었지만, 결점을 발견하자마자 정석이고 비교적 간결한 풀이가 떠올라서 얘도 패스했다.

 

 

간단했던것이다.

나무판 전체에 대한 반복문
	옮겨다니는 필터에 대한 반복문
    	B체스판과의 일치 개수 연산
        W체스판과의 일치 개수 연산
        
    현재 저장된 최솟값과 , B연산, W연산 셋 중 최소를 현재 최소에 저장
끝..

이렇게하면되는거였다!!!!!!!!!

 

체스판이랑 무지성으로 비교해 보고, 다른 값의 개수를 세어 fixer1, fixer2에 저장했다.

현재 저장된 최솟값은, 지금까지 나무판 속 필터들을 돌면서 기록된 가장 작은 값이다.(fixer에 저장)

이 fixer과 fixer1, fixer2중 최솟값을 다시 fixer에 저장한다.

int fixer = min(fixer, min(fixer1, fixer2))

이렇게 구현했다. fixer1과 fixer2중 찾은 최솟값을, fixer과의 최소 비교 과정이다.

 

이 과정을 나무판 다 돌 때까지 반복하면 된다.

#include <algorithm>
#include <cmath> //C++
#include <iostream>
#include <math.h> //C
#include <string>
#include <vector>

using namespace std;

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m;
  cin >> n >> m;
  vector< vector <char>> v(n, vector<char>(m));
  
  for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin >> v[i][j]; }}

  char B[8][8] = {
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'}
  };

  char W[8][8] = {
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'},
  {'W','B','W','B','W','B','W','B'},
  {'B','W','B','W','B','W','B','W'}
  };
  
  int fixer1=0, fixer2=0;
  int fixer = 1000;
  for(int i=0; i<=n-8; i++){
    for(int j=0; j<=m-8; j++){
      for(int k=i; k<i+8; k++){ 
        for(int l=j; l<j+8; l++){
          if(v[k][l] != B[k-i][l-j]) fixer1++;
          if(v[k][l] != W[k-i][l-j]) fixer2++;  
        }
      }
      fixer = min(fixer, min(fixer1, fixer2));
      fixer1=0, fixer2=0;
      }
  }
  cout << fixer;
  
  return 0;
}

바보같은 삽질을 했다. 하지만 나름의 논리적인 사고라고 생각했고, 그속에서 결함을 발견했고 수정했고 발견했고 수정해서 답지 없이 문제 해결했다. 박수!