문제
접근 방법
각 (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; }