[백준 / BOJ] - 1018번 체스판 다시 칠하기 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1018] 체스판 다시 칠하기

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

 

문제

 

M*N 크기의 보드를 잘라 8x8크기의 체스판을 얻으려고 하는데, 주어진 보드에서 8x8 체스판을 만들때, 가장 적게 색칠하는 횟수를 구하는 문제이다. 

입력으로는 N과 M, 행과 열 사이즈를 입력하고 보드가 어떻게 생겼는지를 B(Black)와 W(White)로 구분하여 입력한다.

 

 

풀이

 

해당 문제는 Brute Force 방식으로 해결하면 되는 문제이다. 모든 경우의 수를 모두 계산해본 후, 가장 재색칠이 적었던 경우를 출력해주면 된다. 체스판의 형태는 항상 2가지 형태로 고정되어있는데, 한가지는 검정색으로 시작하는 경우와 흰색으로 시작하는 경우이다.

이를 미리 string 배열로 만들어준다.

 

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

 

결국 재색칠해야하는 횟수는 저 두가지의 체스판과 다른 색깔의 총합을 구하면 알 수 있는것이다.

이때 절대 간과해서는 안되는것이, WB, BW를 모두 고려해야한다는것이다. 이 문제의 오답률이 높은 이유는 대부분의 사람들이 주어진 필드가 검은색으로 시작했다면 BW로 생긴 체스판과 비교를 하며 최소값을 찾으려고 하는데, 사실 제일 처음 필드를 W로 재색칠하고 시작하는 경우가 더 최소값일 수 있다.

 

그래서 시작이 검정색일 경우와, 흰색일 경우를 각각 고려해서 함수를 짜서 문제를 해결하였다.

 

int WB_cnt(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(board[x+i][y+j] != WB[i][j])
                cnt++;
        }

    }
    return cnt;
}

int BW_cnt(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(board[x+i][y+j] != BW[i][j])
                cnt++;
        }

    }
    return cnt;
}

 

배열의 좌표 x,y를 받아온 후, 해당 위치를 첫 필드로 가지는 체스판이 검정색으로 먼저 시작할 경우 몇 번의 수정이 필요한지를 구하는지를 구하는 BW_cnt함수와 흰색으로 먼저 시작할 경우 몇 번의 수정이 필요한지를 구하는 WB_cnt 함수를 선언하였다.

 

그 후, 입력받은 보드의 크기를 고려하여, 8x8의 체스판을 생성할 수 있는 범위를 정하여, BW_cnt와 WB_cnt함수를 호출하고, 이중에 더 작은 값을 찾아가며 for문을 호출한다.

 

    for(int i = 0; i + 8 <= N; i++)
    {
        for(int j = 0; j + 8 <= M; j++)
        {
            int tmp;
            tmp = min(WB_cnt(i,j),BW_cnt(i,j));
            if(tmp < min_val) {
                min_val = tmp;
            }
        }
    }

 

위와 같은 호출을 통해, 만들 수 있는 모든 체스판과 재색칠이 필요한 횟수를 구할 수 있다.

그리고 최종적으로 제일 작았던 값이 저장된 min_val을 출력시켜주면 해당 문제를 해결할 수 있다.

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
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 WB_cnt(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(board[x+i][y+j] != WB[i][j])
                cnt++;
        }

    }
    return cnt;
}
int BW_cnt(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(board[x+i][y+j] != BW[i][j])
                cnt++;
        }

    }
    return cnt;
}
int main() {
    int size[2];
    int cnt;
    int min_val = 12345;
    pair<int, int> p1;
    cin >> p1.first >> p1.second;
    for(int i = 0; i < p1.first; i++)
        cin >> board[i];
    for(int i = 0; i + 8 <= p1.first; i++)
    {
        for(int j = 0; j + 8 <= p1.second; j++)
        {
            int tmp;
            tmp = min(WB_cnt(i,j),BW_cnt(i,j));
            if(tmp < min_val) {
                min_val = tmp;
            }
        }
    }
    cout << min_val;
    return 0;
}

 

 

 

평가

 

좌표계나 행렬 인덱스를 저장하기 좋은 pair라는 STL 자료형을 사용하며 공부할 수 있었던 문제이다.

또한 Brute Force 알고리즘의 대표적인 예시로, Brute Force는 이런 방식으로 풀이하면 된다는 느낌으로 포스팅을 진행하였다.