[BOJ 15999] 뒤집기

풀이

만약 n개의 뒤집을 수 있는 타일이 있다고 했을 때 전체 타일 모양의 개수를 2^n개가 된다.

하지만 여기서는 초기 상태가 정해져 있고 하나의 타일을 누르게 되면 4방향의 색깔이 같으면서 인접한 타일도 같이 움직이기 때문에 누를 수 있는 타일과 누를 수 없는 타일로 구분된다.

초기 상태를 유지하기 위해서는 4방향의 인접한 타일들이 모두 같은 색깔이면 상태를 계속 유지할 수 있지만 다른 색깔이 있으면 2번 이상 타일을 움직이게 되면 초기 상태를 유지하지 못하게 된다.

그렇기 때문에 현재 타일을 기준으로 4방향을 조사하여 색깔이 다른 타일이의 유무를 조사하고 전체에서 서로 다른 색깔이 인접해 이는 타일의 개수를 파악한다.

그리고 전체 N * M개의 타일에서 다른 색깔로 인접된 타일의 개수를 뺀 값을 2의 제곱을 해주면 정답을 찾을 수 있다.

여기서 N,M <= 2000이기 때문에 2의 제곱연산에서 오버플로우를 조심해야 한다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m;
string arr[2001];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				int r = i + dy[k];
				int c = j + dx[k];

				if (r < 0 || c < 0 || r >= n || c >= m) continue;
				else if (arr[i][j] != arr[r][c]) {
					cnt++;
					//현재 색깔과 다르면 체크
					break;
				}
			}
		}
	}

	int ans = 1;
	// 전체에서 체크된 개수를 뺀 만큼의 타일만 움직일 수 있음
	for (int i = 0; i < (m * n - cnt); i++) {
		ans = (2 * ans) % 1000000007;
	}
	cout << ans;

	return 0;
}