백준 1018번[brute force] - 체스판 다시 칠하기문제 C++ 초기값 설정

📍 백준 1018번 - 체스판 다시 칠하기문제 C++  

 

 

🧩 문제 요약

입력이 주어질 때 8*8체스보드를 만들기 위해서 최소 몇개의 보드를 칠해야하는지 구하라. 

 

 

 

👍 이 문제에서 배운점 

 

😕 문제점 1.

먼저 이 문제를 풀때 brute force문제인데 어떻게 풀어야할지 몰라서 감이 안잡혔다. 

처음에는 체크보드와 제일 유사도가 높은 부분을 배열에서 찾아내고 그 다음 몇개를 색칠해야 할지 계산하는 식으로 문제를 풀어보려고 했는데, 비약이 너무 많았다. 하지만 다른 방법은 생각도 안나고 결국은 다른 사람들의 풀이를 살펴보았다. 

 

✅ 해결방법 : 정상적인 체크보드와 비교하기 

string WB[] = 
{
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};

string BB[] = 
{
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
};

 

해결책은 정상적인 체크보드와 비교하는 것이다. 

문제에서도 나와있듯이 체크보드는 결구 흰색으로 시작하는 것, 검정색으로 시작하는 것 이 두가지 경우 밖에 없다. 

그래서 정상적인 체크보드와 비교해서 최소한 칠할 수 있는 부분을 찾으면 된다. 

 

그래서 구현한 코드가 아래와 같다. 

#include <iostream>
#include <string> 
#include <vector> 
using namespace std; 

string WB[] = 
{
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};

string BB[] = 
{
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
};

vector<string> input_board;

int findMinB(int a, int b){
    cout << "findMinB funtion is working\n";
    int i, j, cnt; 
    for(i=a; i<a+8; i++){
        cout << "Now, finding a wrong section.... \n";
        for(j=b;j<b+8; j++){
            if(BB[i][j] != input_board[i][j]) cnt++;
        }
    }
    return cnt ; 
}

int findMinW(int a, int b){
    cout << "findMinW funtion is working\n";
    int i, j, cnt; 
    for(i=a; i<a+8; i++){
        cout << "Now, finding a wrong section.... \n";
        for(j=b;j<b+8; j++){
            if(WB[i][j] != input_board[i][j]) cnt++;
        }
    }
    return cnt ; 
}

int main(){
    int n, m, i, j ; 
    cin >> n >> m ; 
    string str;
    
    for(i=0; i<n; i++){
        cin >> str; 
        input_board.push_back(str);
    }

    cout << "Checking...\n" ; 
    for(i=0; i<n; i++){
        cout << input_board[i] << "\n";
    }

    int minval = 65, tmp, b_result, w_result ;
    for(i=0; i+8<=n; i++){
        for(j=0; j+8<=m ; j++){
            b_result = findMinB(i,j);
            w_result = findMinW(i,j);
            cout << "findMinB result : " << b_result << ", findMinW reslut : " << w_result << "\n";
            tmp = min(b_result, w_result);
            if(tmp<minval){
                cout << "minval is changing : " << tmp << "\n" ;
                minval = tmp;
            }
        }
    }
    cout << minval << "\n"; 
}

 

 

😕 문제점 1.

하지만 이 코드에서 findMinB와 findMinW의 return 값이 아래와 같이 이상한 값이 나온다는 것이다. 

findMinB result : 4219106, findMinW reslut : 4219107

 

이유를 생각해보니 함수 내에서 cnt의 초기값을 안 넣어준것이 문제였다. 

C계열에서는 초기화를 하지 않으면 변수에 쓰레기 값을 할당해준다. 

그래서 쓰레기값이 들어있는 상태에서 cnt++이라고 해버리니까 쓰레기값에 더하기가 되고 이상한 값이 나왔다. 

 

 

✅ 해결방법 : 변수 초기값 설정해주기 

해결방법은 매우 간단하다. 

int findMinW(int a, int b){
    cout << "findMinW funtion is working\n";
    int i, j, cnt=0; 
    for(i=a; i<a+8; i++){
        cout << "Now, finding a wrong section.... \n";
        for(j=b;j<b+8; j++){
            if(WB[i][j] != input_board[i][j]) cnt++;
        }
    }
    return cnt ; 
}

 

이렇게 cnt의 초기값을 0으로 설정해주면 된다. '

 

 

 

여담) BB, WB vector선언할 때 ',' 하나를 안찍어서 한참을 뭐가 문제인지 살펴보았다. 

다들 코드 잘 확인하자...-_-