이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 7 번째 글 입니다.
목차
실버5 : 완전 탐색 문제이다.
대표적인 완전 탐색 문제이다. 체스판이 될 수 있는 모든 경우에 대해서 몇번의 flip을 해야하는지 세고, 이를 갱신해주면 풀린다. 이 때, 체스판의 규칙을 잘 파악하는 것이 중요하다.
Example
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 1 | W | B | W | B | W | B | W | B |
| 2 | B | W | B | W | B | W | B | W |
| 3 | W | B | W | B | W | B | W | B |
| 4 | B | W | B | B | B | W | B | W |
| 5 | W | B | W | B | W | B | W | B |
| 6 | B | W | B | W | B | W | B | W |
| 7 | W | B | W | B | W | B | W | B |
| 8 | B | W | B | W | B | W | B | W |
1행에서, 맨 마지막인 8열은 B이고, 그 다음 행의 첫번째는 B이다. 계속해서 엇갈려서 발생하는 것이 아니고, 행이 끝날 때, 마지막 요소가 다음 요소가 된다. 또한 추가적으로 체스판은 시작 위치의 표식이 어떤 것이냐에 따라 모양이 정해진다. 이 부분에서 생각할 수 있는 것은, 같은 모양이나 시작 위치의 표식만 바뀐다. 라는 것이다.
구현
이 것을 구현하기 위한 단계를 생각해보자.
- 우리는 체스판의 크기에 따라 몇 개의 작은 체스판을 조사해야 하는지 정해야 한다.
- 그 안에 들어갔을 때, 시작 위치의 표식을 설정해 주어야 한다.
- 체스판을 만들 수 있는 방법을 진행하며 다른 부분을 체크하고 count 해야한다.
Code
// 실버5 : 백준 1018번 체스판 다시 칠하기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool map[50][50];
int N, M;
int ans = 2000000000;
void go(int y, int x){
// 각각의 작은 체스판에서 시작 위치의 표식을 W, B으로 설정한다.
// bool으로 잡았기 때문에 0 또는 1로 모델링이 가능하다.
for (int mode = 0; mode <= 1; mode++) {
int localAns = 0;
for (int i = y; i < y+8; i++) {
// 이 부분이 행이 끝났을 떄 표식을
// 다음행에 가져가도록 하는 코드이다.
mode = !mode;
for (int j = x; j < x+8; j++) {
if (mode != map[i][j]) {
localAns++;
}
mode = !mode;
}
}
// 각각에 대해 ans를 업데이트 해준다.
ans = min(ans, localAns);
}
}
int main(){
cin >> N >> M;
// 1, 0으로 바꿔서 넣어주었다. W = 1, B = 0
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
char temp;
cin >> temp;
if (temp == 'W') map[i][j] = 1;
else map[i][j] = 0;
}
}
// 체스판 모양에 따라 발생할 수 있는
// 작은 체스판의 시작 위치를 결정한다.
for (int i = 0; i <= N-8; i++) {
for (int j = 0; j <= M-8; j++) {
go(i, j);
}
}
cout << ans <<'\n';
}