[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘

백준 1018번 체스판 다시 칠하기

( 실버 4 ) 

 

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

1018번: 체스판 다시 칠하기

 

 

(정답 코드)

#include <iostream>
#include <vector>

using namespace std;

// 8x8 규격 내 바꿔야하는 칸 수 체크하는 함수
int check(int x, int y, const vector<vector<char>>& bw, char ch) {
    int cnt_change = 0;
    
    for(int i=0; i<8; i++) {
        for(int j=0; j<8; j++) {
            
            if(i%2 == 0 && j%2==0) { // 둘다 짝수
                if(bw[x+i][y+j]==ch) continue;
            } 
            
            else if (i%2 == 1 && j%2==1){ // 둘 다 홀수
                if(bw[x+i][y+j]==ch) continue;
            } 
            
            else { // 이외의 경우
                if(bw[x+i][y+j]!=ch) continue;
            }
            
            cnt_change++; // 위에 해당하는 올바르게 배치된 경우가 아니면, 바꿔야하는 횟수 +1
        }
    }
    
    return cnt_change;
}

// 주어진 nxm에서 가능한 모든 8x8을 검사하도록 하며, 바꿔야하는 칸 수가 가장 적은 것을 찾는 함수
int findMinChange(int n, int m, const vector<vector<char>>& bw) {
    int cur_min = 0;
    int last_min = 8*8+1;
    
    for(int y=0; y<=m-8; y++) {
        for(int x=0; x<=n-8; x++) {
            
            // 좌표 x,y부터 8x8 칸에 바꿔야하는 최소 갯수
            cur_min = min(check(x, y, bw, 'B'), check(x, y, bw, 'W'));
            
            // last_min 갱신
            if(cur_min < last_min) {
                last_min = cur_min;
            }   
        }
    }
    
    return last_min;
}

int main()
{
	// 속도 향상 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n, m, x;
    string str; 
    
    cin >> n >> m ;
    
    vector<vector<char>> bw (n, vector<char>(m));
    
    // 체스판 입력받기
    for(int j=0; j<n; j++) {
        cin >> str;
        for(int i=0; i<m; i++) {
            bw[j][i] = str[i];
        }
    }
    
    // 최종 연산 및 출력
    cout << findMinChange(n, m, bw);

    return 0;
}

 

 

 

📖 풀이 요약

 

 한 마디로 주어진 입력 내의 가능한 모든 8x8을 모두 검사한 것이다. (브루트포스 알고리즘)

 

 주어진 n x m 칸을 각각 char 이차원 벡터(bw)에 넣고, 8x8 크기의 규격만큼을 모두 검사하며, B로 시작하는 경우, W로 시작하는 경우 각각에서 틀리게적혀있어 바꿔야하는 갯수를 카운트했다. 그 중 가장 적었던 카운트 값을 출력한다. 

 

 

사용된 연산 함수 설명:

 

1. findMinChange(n, m, bw)

• 모든 8행 8열의 모든 규격을 검사하기 위해서, x,y 변수를 각 규격의 시작점으로 설정했다.
• n x m 크기의 바둑판에서 x행 y열을 기준으로 8x8 규격이 B 또는 W로 시작하는 경우의 바꿔야하는 칸 수를 check 함수로 각각 구하고, 둘 중 더 작은 값을 cur_min에 저장한다.
• 그리고 현재까지의 값보다 cur_min이 더 적다면, 최종 최솟값을 저장하는 last_min 변수를 갱신해 저장해준다.

2. check(x, y, bw, ch)

• 좌표 (x, y)에서 시작하는 8x8 영역이 B 또는 W로 시작하는 경우, 바꿔야 하는 돌의 개수를 반환한다.
• B로 시작한다면, 모든 (짝수행, 짝수열) (홀수행, 홀수열)에는 B가 있어야하고, 나머지는 W가 있어야한다.
   W로 칸이 시작하는 경우도 같은 규칙이다.
• B,W가 올바르게 적혀있다면 continue로 무시, 아니라면 카운트를 +1 해줬다.

 

문제 풀이

 

 

 

 

복잡해보이지만.. 예제를 보면서 차근차근 규칙 찾고, 검사하는 과정을 구현하면 금방 풀리는 문제 !