[c++] 백준 15999 - 뒤집기 [카카오 코딩 페스티벌 18]

 

사진귀여움

---

이왜맞? 을 한 문제였다.

 

현재 상태를 만들 수 있는 격자판을 만드는 문제이다.

반대로 뒤집어서 생각하면 현재 상태에서 새로 만들 수 있는 상태를 찾아내는 문제이다.

 

따라서 현재 상태를 바꿀 수 있는 경우를 모두 고르면 된다.

 

우선 위 예시를 보면

 

W	B
B	B

이라는 상태인인데, w를 누르는 순간 모든 격자가 B로 통일되버리니 누를 수 없다. (다시 복구할 수 없기 때문)

[0,1]의 B버튼을 눌러도 W랑 통합이 되어버리고, [1,0]도 마찬가지이다.

오직 오른쪽 아래 [1,1] B버튼만이 누를 수 있다. 

즉, 양옆에 다른 색이 붙어있다면 해당 색과 통일되어 버려서 누를 수 없다.

모든 붙어있는 면이 같은색이면 누를 수 있다. 

 

그리고 나는 문제를 풀 때 이 예시를 생각했다.

 

W	W	W	W
W	W	B	W
W	B	B	B
W	W	B	W

이런 예를 생각해보자.

이런 예시를 생각해 봐도 이 상태에서 새로운 상태를 만들어낼 수 있는건 붙어있는 모든 면이 같은색일 때라는걸 유추할 수 있다. 

만약 그렇지 않으면 색이 통합되버려 다시 되돌릴 수 없다.

 

그러면 간단하게 문제를 풀 수 있다.

입력을 받고, 모든 붙어있는면이 같은색인것의 개수를 구해서 (num으로 구현)

2의 거듭제곱을 해주면 된다. 

해당 격자가 W인지 B인지 둘중에 하나이기 때문이다.

#include <bits/stdc++.h>
using namespace std;
bool arr[2000][2000] = {false,};

int main(){
    int x[4] = {-1,0,1,0} , y[4] = {0,1,0,-1};
    int N,M,num=0,a,b,answer=1;    cin>>N>>M; 
    bool plus;
    string str;
    for(int i=0; i<N; i++){ cin>>str;
        for(int j=0; j<M; j++){
            arr[i][j] = (str[j] == 'W') ? true : false;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            plus = true;  //모든 변이 같은지 상태 저장하는 bool
            for(int k=0; k<4; k++){
                a = i+x[k] , b = j+y[k];
                if(a>=0 && b>=0 && a<N && b<M){
                	//같지 않은게 있으면 plus를 false 하고 바로 break
                    if(arr[a][b] != arr[i][j]){
                        plus = false; break;
                    }    
                }
            }
            //같으면 num을 늘려준다.
            if(plus) num++;
        }
    }
    //num만큼 2를 곱해줌
    for(int i=0;i<num;i++){
        answer *= 2;
        answer %= 1000000007;
    }
    cout<<answer;
}