[1018번] 체스판 다시 칠하기

백준 1018번: 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

저희들이 한 번쯤은 접해본 체스판의 모양에 대한 문제입니다.

체스판에 있는 각 사각형들의 패턴은 검은색과 하얀색이 번갈아 칠해지는 것이라 할 수 있습니다.

지민이는 잘못 칠해진 체스판의 색을 다시 패턴에 맞게 칠하고 싶어 합니다.

이때 그 최소 횟수를 구하는 문제입니다.

---

▶ 입력

첫째 줄에 N과 M이 주어진다. M과 N은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개 줄에는 체스판의 색 상태가 주어진다. B는 검은색이며, W는 흰색이다.

▶ 출력

첫째 줄에 지민이가 8*8 크기로 자른 뒤에 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

저는 처음에 패턴이라는 단어 꽂혀서 패턴을 찾을 수 있는 코드를 짜야하는 줄 알았습니다.

하지만 잘 생각해보니 패턴에 따라 반복문과 조건문을 적절히 섞기에는 많은 조건들이 필요하다는 것을 알게 되었고,

결국 다른 방법을 강구하게 되었습니다.

 

먼저 제한 조건을 보면, "시간제한 : 2초/ 메모리 제한 : 128 MB"라고 되어 있습니다.

이걸 보고 저는 브루트 포스(Brute Force) 기법을 이용한다면 그다지 어려운 방법이 아닐 것 같다고 생각했습니다.

그 이유는 시간도 넉넉하다고는 말 못 하지만, 체스판의 크기가 최대 50 x 50 정도로 사실 그리 큰 편이 아니라는 것입니다.

최대 연산 횟수(최대 크기의 체스판 & 64번의 고정 연산)가 ' (43 x 43) x 64 = ‭118,336‬‬ '번이라고 할 수 있습니다.

이 정도 연산 횟수면 컴퓨터한테는 잠깐 스쳐가는 바람 정도만큼만 걸릴 것입니다.

 

그래서 저는 미리 두 가지 Dataset ( 맨 위쪽의 가장 왼쪽이 검은색 B로 시작하는 체스판 / 흰색 W로 시작하는 체스판 )을 미리 준비하고

이 둘을 자른 각 체스판과 모두 직접 비교해서 각각 바꿔야 하는 패턴의 개수를 일일이 셌습니다.

 

나머지는 그 두 수 중 최소를 출력하면 끝나겠죠?

사용 언어: C++

#include <bits/stdc++.h>
using namespace std;

string d1[8] = {
    "WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW"
};
string d2[8] = {
    "BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB"
};

int main() {
    ios_base::sync_with_stdio(false);
    string s[50];
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; ++i) cin >> s[i];
    
    int ans = 64;
    for(int i = 0; i <= n - 8; ++i) {
        for(int j = 0; j <= m - 8; ++j) {
            // 분리된 각 판에서 바꿔야 하는 패턴 개수 세기
            int cnt1 = 0, cnt2 = 0;
            for(int k = 0; k < 8; ++k)
                for(int l = 0; l < 8; ++l) {
                    if(s[i + k][j + l] != d1[k][l]) ++cnt1;
                    if(s[i + k][j + l] != d2[k][l]) ++cnt2;
                }
            ans = min(ans, min(cnt1, cnt2));
        }
    }
    
    printf("%d", ans);
}

---

머리 복잡하게 굴리는 것보단 연산의 크기가 크지 않고 패턴 찾기에 따라 코딩하기 어렵다면

조건에 따라 브루트 포스라는 방법을 사용할 수도 있다는 것을 항상 염두에 두어야겠습니다.