백준[1018] - 체스판 다시 칠하기

문제

백준 1018 문제 보기

접근 방법

각 (0, 0)부터 (N - 7, M - 7)까지 8 * 8의 죄판을 그릴 수 있다. 각 점을 돌면서 B, W를 한번씩 수행하고 정답을 출력한다.

코드

#include <iostream>
#include <cstring>
using namespace std;
int N, M;
int map[51][51];
int map_copied[51][51];
int check[51][51];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int sr, sc;
int cnt, ans = 987654321;
void brute(int r, int c, int num) {
// 현재 좌표가 가져야할 색이 아니면
if(map_copied[r][c] != num) {
// 색을 바꾸고
map_copied[r][c] = num;
// 카운트 증가
cnt ++;
}
// 방문 체크
check[r][c] = 1;
// 4방향 검사
for(int i = 0; i < 4; i ++) {
int nextR = r + dr[i];
int nextC = c + dc[i];
if(nextR >= sr && nextC >= sc && nextC < sc + 8 && nextR < sr + 8){
if(!check[nextR][nextC]) {
// 다음 색은 현재 색과 무조건 대치
brute(nextR, nextC, -num);
}
}
}
}
int main() {
cin >> N >> M;
for(int i = 0; i < N; i ++) {
for(int j = 0; j < M; j ++) {
char temp;
scanf(" %c", &temp);
if(temp == 'W') {
// 흰색이라면 1 저장
map[i][j] = 1;
} else {
// 검정이라면 -1 저장
map[i][j] = -1;
}
}
}
// 8 * 8 모든 범위 계산
for(int i = 0; i < N - 7; i ++) {
for(int j = 0; j < M - 7; j ++) {
// map 복사
memcpy(map_copied, map, sizeof(map));
// 방문 여부 초기화
memset(check, 0, sizeof(check));
// 시작 위치 저장, 카운트 초기화
sr = i, sc = j, cnt = 0;
// 검정색부터 완전 탐색 시작
brute(i, j, -1);
// 최소 저장
ans = min(ans, cnt);
memcpy(map_copied, map, sizeof(map));
memset(check, 0, sizeof(check));
cnt = 0;
brute(i, j, 1);
ans = min(ans, cnt);
}
}
cout << ans;
return 0;
}
Share