문제 이해
- M * N 크기의 보드가 주어진다.
- 보드는 검은색 또는 흰색으로 칠해져있다.
- 이 보드로 체스판을 만들 예정인데 8 * 8 크기이고, 검은색과 흰색이 번갈아 칠해져야 한다.
- 체스판은 그러므로 맨 왼쪽 위칸이 흰색인 경우와 검은색인 경우 두 가지만 존재한다.
- 8 * 8 크기로 자른 뒤, 다시 칠해야 하는 정사각형의 최소 개수를 구하라.
<입력>
- N, M; 보드의 크기 (8 ~ 50)
- B: Black
- W: White
<출력>
- 8*8로 자른 뒤 다시 칠해야하는 정사각형 개수의 최솟값
<조건>
- 시간 제한: 2초
- 메모리 제한: 128MB
문제 풀이
브루트포스 혹은 분할정복을 써야한다고 생각했는데
보드의 크기가 작아 브루트포스로도 충분히 풀 수 있다고 생각했다.
처음에는 8*8로 자른 뒤, 처음 시작이 W인것과 B인것으로 하여
현재 블록과 다음 블록을 비교하는 식으로 칠해야하는 개수의 최솟값을 구하려고 했다.
분명 위의 방법도 구현하는 방법이 있겠지만 구현에 애를 먹었고,
인터넷의 풀이를 참조한결과 처음부터 체스판 두 개를 선언해둔 뒤, 비교하는 방식을 찾을 수 있었다.
구현 방식도 훨씬 간단했다.
char WB[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'
};
char BW[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'
};
현재 블록과 다음 블록을 비교하는 방식에서
가능한 체스판의 경우의 수로 비교하는 방식으로 넘어가며, for문 조건문의 수정이 필요했는데
캐치하는데 조금 시간이 걸렸다.
for(int k = i; k < i+8; k++){
for(int l = j; l < j+8; l++){
if(map[k][l] != WB[k][l]){
tmpAns1++;
}if(map[k][l] != BW[k][l]){
tmpAns2++;
}
}
}
위의 코드의 문제가 보이는가?
바로 i와 j가 0일경우 잘 작동하지만,
만약 1이상이되면 WB와 BW배열에서 잘못된 인덱스에 접근하게 된다.
이런 사소한 반복문에서의 실수를 주의하도록 하자.
아래는 제대로 고친 코드이다.
for(int k = 0; k < 8; k++){
for(int l = 0; l < 8; l++){
if(map[i + k][j + l] != WB[k][l]){
tmpAns1++;
}if(map[i + k][j + l] != BW[k][l]){
tmpAns2++;
}
}
}
전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
char map[55][55];
char WB[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'
};
char BW[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'
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin>>n>>m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin>>map[i][j];
}
}
int ans = 987654321;
for(int i = 0; i <= n-8; i++){
for(int j = 0; j <= m-8; j++){
int tmpAns1 = 0, tmpAns2 = 0;
for(int k = 0; k < 8; k++){
for(int l = 0; l < 8; l++){
if(map[i + k][j + l] != WB[k][l]){
tmpAns1++;
}if(map[i + k][j + l] != BW[k][l]){
tmpAns2++;
}
}
}
tmpAns1 = min(tmpAns1, tmpAns2);
ans = min(tmpAns1, ans);
}
}
cout<<ans;
return 0;
}비교해야 할 배열의 경우의 수가 적다면,
꼭 주어진 배열 안에서 비교할 필요가 없이 미리 선언한 뒤 비교하는 방식도 있다는 걸 배울 수 있었다!