C++) 백준 1018번: 체스판 다시 칠하기

코딩 테스트 관련 포스팅은 당초 계획에 있지는 않았으나,

1. 풀었지만 다른 사람의 풀이가 너무 좋은 경우

2. 풀지 못하고 다른 사람의 풀이를 참고한 경우

에는 정리 겸 글로 남기는 것도 나쁘지 않을 것 같다고 판단하여 하나씩 채워보려 한다.

 

이번 문제는 백준 1018번이다.

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

1018번: 체스판 다시 칠하기

 

< 접근 방식 1 - 실패 >

좌측 상단 모서리를 기준으로 B인지 W인지 체크한 후, 체스판을 만들어서 최솟값을 구했다.

무언가 느낌이 이상해서 문제를 다시 생각해보니 좌측 상단 모서리가 B인지 W인지 체크하는 것이 아니라 B도 될 수 있고 W도 될 수 있는 것이었다. 따라서 문제 해석을 잘못함.

문제를 똑바로 읽고 이해부터 하자.

 

< 접근 방식 2 - 실패 >

이번엔 문제는 제대로 이해한 듯 하다.

1. 좌측 상단 모서리를 기준으로 B일 떄 W일 때를 모두 염두에 두고 8 x 8 체스판을 둘 다 만들어 최솟값을 하나씩 확인해본다.

2. 8 x 8 체스판을 만들 때는 반복문의 조건자(보통 i, j 등으로 쓰는 것)를 짝수 혹은 홀수를 기준으로 B나 W의 값이 본래 있어야하는 값과 다르면 count를 센다.

e.g)

if (i % 2 == 0 && j % 2 == 0) {

  if (arr[i][j] == 'W') count++;

}

대충 이런 식인데...식이 굉장히 복잡해졌다. 맞았다면 그나마 다행인데, 하필 TC가 모두 통과되지 않아서 보기도 힘든 코드를 수정하느라 굉장히 애먹었다. 근데 결국 이렇게 하고도 안됐음. 한 1시간 반 정도 보다가 다른 풀이를 택하기로 했다.

 

< 접근 방식 3 - 성공 >

옛날에 DP 문제들을 풀 때, 모양을 만들어 놓는 것을 차용하여 배열을 미리 만들어놓고 비교하는 것을 선택했다.

1. 8 x 8의 BWBW ... 배열과 WBWB ... 배열을 미리 만들어 놓음.

2. 좌측 상단 모서리를 기준으로 8 x 8 배열을 미리 만들어 놓은 배열과 비교하여 다른 것만 바꿔주고 count를 셈.

처음부터 이렇게 할 걸 그랬다. 코드도 훨씬 단순해지고 시간도 적게 걸렸다. 역시 문제 풀이는 처음에 길을 잘 들어가는 것이 베스트인 듯. 물론 그게 어려운 거겠지만..

 

아래는 전체 코드이다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

char bw[8][9] = {
{'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 wb[8][9] = {
{'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 main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int N, M;
cin >> N >> M;

char** arr_original = new char* [N];
for (int i = 0; i < N; i++) {
arr_original[i] = new char[M];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> arr_original[i][j];
}
}

int count_bw = 0;
int count_wb = 0;
int min = 65;
for (int i = 0; i <= N - 8; i++) {
for (int j = 0; j <= M - 8; j++) {
for (int k = i, m = 0; k < i + 8; k++, m++) {
for (int l = j, n = 0; l < j + 8; l++, n++) {
if (bw[m][n] != arr_original[k][l]) {
count_bw++;
}
if (wb[m][n] != arr_original[k][l]) {
count_wb++;
}
}
}
if (min > count_bw)
min = count_bw;
if (min > count_wb)
min = count_wb;
count_bw = 0;
count_wb = 0;
}
}

cout << min;

for (int i = 0; i < N; i++) {
delete[] arr_original[i];
}
delete[] arr_original;

return 0;
}