백준 1018 - 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

문제 설명

---

N*M 메트릭스에서 임의로 8*8 메트릭스만큼 잘랐을때 다시 칠해야 하는 최소 개수를 구하는 문제이다. 

(단, 문제에서 말한 것처럼 인접한 것은 서로 다른 색을 가지고 있다. 'W','B')

 

 

접근 방식

---

위 방법은 전형적인 브루트 포스 방식을 사용하면 간단하게 풀이 가능하다.

8*8의 행렬을 두개 준비하고 브루트 포스 방식으로 비교를 하면서 최소값을 찾는다.

 

 

코드

---

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
int n,m;
int cnt1=0,cnt2=0;
int mini=9876543;
string map[51];
string map1[8] = {	//0,0이 W인경우
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
};
string map2[8] = {	//0,0이 B인경우
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
};
void bf(int rlen,int clen){
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(map1[i][j]!=map[rlen+i][clen+j]) cnt1++;	//다른 경우 비교
            if(map2[i][j]!=map[rlen+i][clen+j]) cnt2++;
        }
    }
    mini=min(mini,min(cnt1,cnt2));	//최소값 구하기
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        cin>>map[i];
    }
    int rlen,clen;	//8*8행렬이 row, column으로 이동할수 있는 거리:rlen,cle
    rlen=n-8;clen=m-8;
    for(int i=0;i<=rlen;i++){	//broute force
        for(int j=0;j<=clen;j++){
            cnt1=0;cnt2=0;
            bf(i,j);
        }
    }
    cout<<mini<<"\n";
    return 0;
}

 

 

funny algorithms :0 ~