[BOJ] 15999 뒤집기

문제 링크

 

www.acmicpc.net/problem/15999

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

격자판의 초기상태로 가능한 경우의 수는, 눌러서 최종 상태로 갈 수 있는 격자의 수를 n이라 하면 2^n가지가 나올 수 있다. 이러한 격자를 누를 수 있는 격자라고 해보자. 누를 수 있는 격자의 수는 어떻게 구해야 할까?

 

최종 상태의 격자판에서 두 개의 격자가 배치되는 경우의 수를 생각해보자.

 

 

 

 

 - 1번 경우에서는 다른 상태에서 A를 눌러 이 상태로 올 수 없다. A가 B와 같은 검은색이었다면 A를 눌렀다면 B도 같이  하얀색으로 변했을 것이고, A가 하얀색이었다면 A를 눌러서 검은색으로 바꾸고, 다시 눌러서 하얀색으로 바꿀 때 B도 같이 하얀색으로 바뀌기 때문이다.

 

 - 2번 경우도 마찬가지로 다른 상태에서 A를 눌러 이 상태로 올 수 없다.

 

 - 3번 경우는 다른 상태에서 A를 눌러 이 상태로 올 수 있다. A가 검은색, B가 흰색이라고 생각해보자. A를 누르면 A만  흰색으로 바뀌고, A와 B가 둘 다 흰색인 상태가 된다. A와 B가 둘 다 흰색이라면, A를 짝수 번 눌러 A와 B가 둘 다 흰색인 상태로 바꿀 수 있다.

 

 

예시는 A를 기준으로 오른쪽 격자를 대상으로 생각했지만, 이는 A의 위쪽, 왼쪽, 아래쪽 격자에도 동일하게 적용된다. 따라서 특정 격자가 상, 하, 좌, 우에 있는 격자와 같은 색이라면, 이 격자는 누를 수 있는 격자이다. 2중 for문을 돌려 이러한 격자들의 수를 세고, 그만큼 2의 제곱을 해준 뒤 1,000,000,007로 나눠주면 답을 구할 수 있다. 이때, 최대 가능한 격자의 수가 2,000 * 2,000 = 4,000,000개이므로, 분할정복을 이용해 구해주면 좀 더 빠른 속도로 답을 구할 수 있다.

 

전체 코드는 아래와 같다.

#include <iostream>
using namespace std;
const int MOD = 1e9 + 7; // 15999 뒤집기	
int nxt[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
char board[2000][2000];

// 2의 거듭 제곱을 구하는 함수
long long func(int num) { 
	if (num == 1) return 2;
	long long tmp;
	if (num % 2) {
		tmp = func(num - 1);
		return (2 * tmp) % MOD;
	}
	else {
		tmp = func(num / 2);
		return (tmp * tmp) % MOD;
	}
}

int main() {
	int i, j, k, n, m;
	cin >> n >> m;
	for (i = 0; i < n; i++) {
		cin >> board[i];
	}

	int num = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			char here = board[i][j];
            //누를 수 있는 격자 판정
			for (k = 0; k < 4; k++) {
				int nxtX = i + nxt[k][0], nxtY = j + nxt[k][1];
				if (nxtX < 0 || nxtX >= n || nxtY < 0 || nxtY >= m) continue;
				if (board[nxtX][nxtY] != here) break;
			}
			if (k == 4) {
				num++;
			}
		}
	}
	cout << func(num) << endl;
}