백준 1018 c++ 완전탐색(Brute-force Serch)

원래 티스토리 해보려고 했는데, 귀찮아서 시작 도안하다가

잔머리? 굴려서 푸는 문제 맞히면 기분 좋잖아요? 

그래서 기분 좋아져서 시작해봄

완전 탐색, 브루트 포스(Brute-force)는 그냥 쉽게말해서 가능한 경우를 일일이 다 탐색하는 방법임

근데 브루트포스 문제들은 다 탐색하면 타임 에러가 뜨겠죠?

그래서 어떻게 시간을 최소화하는지에 따라서 문제를 맞히고, 틀리고 가 결정됨

 

여기 문제 보면 알 수 있는 것처럼 브루트 포스 문제는 시간제한이 있음(하나씩 다 검사하다가는 틀린다는 거)

그래서 어떻게 하면 다 대입안 하고, 시간초과 안하고 찾을 수 있을까? 고민해보니까

시작점만 잘 정하면 되겠다고 생각함(어차피 8X8을 구하는 거닌까) 그래서 시작점을 string크기에 따라서 잘 조절만 하면 할 수 있겠다는 생각을 하게 됐음

뭔 소리냐면

8X8이면 배열[0][0]부터 배열[7][7]까지 비교하는 경우의 수밖에 없는 거고 

10X10이면 배열 시작점이 [0][0], [0][1], [0][2], [1][0], [2][0], [1][1], [2][2] 이렇게 되겠죠?

비교하는 String은 미리 만들어 놨습니다. 

자, 그러면 어떻게 비교하는 코드를 만들까? 처음이라서 코드를 이쁘게 캡처 못하겠어가지고 그냥 코드 올림(양해 좀)

 

 

# include <iostream>
# include <vector>
# include <algorithm>
# include <string>
using namespace std;
string WB[8] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};
string BW[8] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"

};

string board[50];
int main(void)
{

    int a, b;
    cin >> a >> b;
for (int i = 0; i < a; i++)
{
    cin >> board[i];

}

    int cnt_bw = 10000;
    int cnt_wb = 10000;
    int n = 0;
    for (int i = 0; i <= a - 8; i++)
    {    
// a에 따른 시작점 조절
        for (int j = 0; j <= b - 8; j++) { // b에 따른 시작점조절
          for (int k = 0; k < 8; k++) {
            for (int r = 0; r < 8; r++) {
                if (board[i + k][j+r] != BW[k][r])
                n++;

             }
         }
         cnt_bw = min(n, cnt_bw);
         n = 0;
         }   

    }

    for (int i = 0; i <= a - 8; i++) {// a에 따른 시작점조절
        for (int j = 0; j <= b - 8; j++) {// b에 따른 시작점조절
            for (int k = 0; k < 8; k++) {
                for (int r = 0; r < 8; r++) {
                if (board[i + k][r + j] != WB[k][r])
                n++;

                }
            }
        cnt_wb = min(n, cnt_wb);
        n = 0;
        }

    }   
    int result = min(cnt_wb, cnt_bw);
    cout << result;

}