[C++] 백준 1018 - 체스판 다시 칠하기

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

<풀이>

1. 보드를 입력받는다.

2. 해당 보드에서 8x8 사이즈로 만들 수 있는 체스판 중, 색칠해야하는 최소 개수를 출력한다.

 

<해법>

모든 경우를 다 해보아야 합니다. 8x8 사이즈의 판을 탐색하면서, 해당 판에서 B 또는 W로 모두 칠해보고 최소값을 갱신합니다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int N, M;
vector<string> map;
int answer;
 
//왼쪽 위가 B인 체스판
string Bchess[] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
};
 
//왼쪽 위가 W인 체스판
string Wchess[] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};
 
//해당 좌표에서 칠하는 페인트의 최소 개수
int minPaintCount(int x, int y) {
 
    //왼쪽 위가 B인 체스판으로 만들 경우
    int BpaintCount = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (map[i + x][j + y] != Bchess[i][j]) {
                BpaintCount++;
            }
        }
    }
 
    //왼쪽 위가 W인 체스판으로 만들 경우
    int WpaintCount = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (map[i + x][j + y] != Wchess[i][j]) {
                WpaintCount++;
            }
        }
    }
 
    //최소값 반환
    return min(BpaintCount, WpaintCount);
}
 
int main() {
 
    //초기화
    answer = -1;
 
    //입력
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string tmp;
        cin >> tmp;
        map.push_back(tmp);
    }
 
    //해법
    for (int i = 0; i <= N - 8; i++) {
        for (int j = 0; j <= M - 8; j++) {
 
            int minPaint = minPaintCount(i, j);
            
            //결과 갱신
            if (answer == -1 || minPaint < answer) {
                answer = minPaint;
            }
        }
    }
 
    //출력
    cout << answer;
 
    //종료
    return 0;
}

 

구현과 브루트포스에 대해 알아볼 수 있는 문제였습니다.