[BOJ] 백준 1018 체스판 다시 칠하기 / 완전 탐색(Brute-force Search)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

💣 문제 이해

1. 입력받을 체스판은 8*8 이상의 크기를 가진다.

2. 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 두 종류의 판으로 만들고자 한다.

3. 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.

4. 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠하려고 한다. 이때, 8*8 크기는 체스판 내 어디서든 고를 수 있다.

5. 다시 칠해야 하는 칸의 최소 개수를 찾아야 한다.

 

완전 탐색(Brute-force Search) 방식을 사용했다.

 

💭 풀이 과정

 

먼저 흰색 칸으로 시작하는 8*8 체스판과 검정색 칸으로 시작하는 8*8 체스판을 string 배열로 만들어두었다.

 

소스코드 진행 방식은 다음과 같다.

 

입력받은 체스판 좌측 상단에서 한 칸씩 이동하며 좌표를 compare 함수로 넘겨주면

 

compare 함수에서는 인자로 넘겨받은 좌표를 좌측상단으로 하는 입력데이터 8*8배열과 미리 만들어둔 흰색 체스판, 검정색 체스판과 비교하여 다른 개수만큼 각각 카운트한다.(wCount, bCount)

그리고 둘 중 더 작은 값을 리턴하게 된다.

 

다시 메인 함수에서는 기존의 result 값과 넘겨받은 compare함수의 결과값 중 더 작은 것을 저장하고,

다음 좌표를 다시 compare 함수로 넘겨준다.

 

작성 언어: C++

 

#include <iostream>
#include <algorithm>
using namespace std;

// 입력 값을 채울 배열(체스판)
char map[60][60] = {0,};

// 맨 좌측 상단 칸의 색이 흰색인 경우
string whiteMap[8] = {
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
};
// 맨 좌측 상단 칸의 색이 검정색인 경우
string blackMap[8] = {
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"}
};

// 미리 만들어둔 체스판과 입력 데이터를 비교해서
// 흰칸으로 시작하는 판과 검정칸으로 시작하는 판 각각 수정해야하는 칸 수를 구하고
// 둘 중 더 작은 수를 리턴한다.
int compare(int tRow, int tColumn){
    int wCount = 0, bCount = 0;
    
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
        	// 흰칸으로 시작하는 체스판을 만들기 위해 수정해야하는 칸 수
            if(whiteMap[i][j] != map[tRow+i][tColumn+j])    wCount++;
            // 검정칸으로 시작하는 체스판을 만들기 위해 수정해야하는 칸 수
            if(blackMap[i][j] != map[tRow+i][tColumn+j])    bCount++;
        }
    }
    // 비교하여 최소값을 리턴한다.
    if(wCount <= bCount)    return wCount;
    else    return bCount;
}


int main(){
    int row, column, result = 99999999;
    
    scanf(" %d %d", &row, &column);
    // 입력 값에 따라 체스판 채우기
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < column; ++j) {
            scanf(" %c", &map[i][j]);
        }
    }
    
    for (int i = 0; i <= row-8; ++i) {
        for (int j = 0; j <= column-8; ++j) {
        	// 가장 최소인 값을 찾아낸다.
            result = min(compare(i, j), result);
        }
    }
    
    cout << result << endl;
    
    return 0;
}

 

🏆 배운 점

 

문제를 처음 봤을 때, 가장 먼저 떠오른 방식이 이 방법이었다.

근데 다른 방법을 찾으려 하다보니 자꾸 실수가 생겨 문제 풀이에 너무 많은 시간이 걸렸다...

 

브루트 포스 방식으로 접근하겠다고 판단한 만큼,(사실 문제 유형 자체가 브루트포스라고 쓰여있긴 하지만;;)

우선 충분히 합리적이라고 판단되면 바로 진행하는 습관을 들여봐야겠다.