BOJ 15999 - 뒤집기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
5 초	256 MB	731	197	156	39.000%

문제

---

어느 날, 네오는 길을 걷다가 격자판 하나를 주웠다. 그 격자판은 N 행 M 열로, 각 격자는 흰색 또는 검은색으로 칠해져 있다.

네오는 이 격자판에는 분명 엄청난 비밀이 숨겨져 있을 것이라고 생각해 나중에 해독을 시도해 보기로 하였다. 아래 그림은 격자판 상태의 예시이다.

네오가 잠시 외출한 사이, 프로도는 네오의 격자판을 이리저리 살펴보았다. 얼마 뒤, 하나의 격자를 누르게 되면 자신을 포함해 그 격자와 연결된 모든 칸들의 색이 반전된다는 사실을 관찰할 수 있었다. 여기서, 두 격자가 연결되었다는 것은 두 격자 사이를 서로 같은 색이면서 변을 공유하는 격자들로만 이동하여 오갈 수 있다는 것을 뜻한다. 집으로 돌아온 네오는 프로도가 격자판의 상태를 바꿔버렸다는 것을 알고 좌절했다. 하지만 최종 상태를 알고 있기 때문에, 초기 상태를 추측할 수 있을 것이라는 희망을 가지기로 했다.

프로도는 격자판을 0번 이상 눌렀다(아직 한 번도 누르지 않은 상태일 수도 있다). 현재 각 격자의 색깔이 주어졌을 때, 격자판의 초기 상태로 가능한 경우의 수를 1,000,000,007(109 + 7)로 나눈 나머지를 구하여라. 두 격자판의 상태가 다르다는 것은, 같은 위치의 격자의 색이 다른 경우가 존재할 때로 정의한다.

입력

---

첫 줄에 격자판의 행의 수 N 과 열의 수 M 이 주어진다. (1 ≤ N, M ≤ 2,000)

둘째 줄부터 N 개의 줄에 걸쳐 현재 각 격자의 색을 나타내는 문자열이 주어진다.

N 개의 줄 중에서 i 번째 줄의 j 번째 문자는 i 행 j 열 격자의 색을 나타내며, 'B'인 경우 검은색, 'W'인 경우 흰색임을 나타낸다.

출력

---

첫 줄에 격자의 초기 상태로 가능한 경우의 수를 1,000,000,007(10^9 + 7)로 나눈 나머지를 출력한다.

접근

---

뚜렷한 접근법이 생각나지 않아서 풀이를 보았다.
핵심은, 누를 수 있는 격자가 몇 개인지를 세는 것이었다.
'고립'된 격자만 누를 수 있는 상태이다.
여기서 고립이란, 범위를 벗어나지 않은 상하좌우 격자가 모두 지금과 같은 상태인 것을 의미한다.
생각해보면 인접한 격자와 같은 색이였으면 색이 달라질 수 없기 때문이다.
이까지 생각했으면 구현은 간단하였다.

풀이

---

2차원 arr 배열을 순회하면서, 인접한 격자와 모두 색이 같은 경우에 cnt 값을 더해준다.
이 격자들은 W, B 두가지 상태를 모두 가질 수 있기 때문에, 2^cnt를 구해주면 정답이 된다.
cnt 값이 충분히 클 수도 있기 때문에, overflow가 나지 않게 매번 MOD로 나눠준다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
const int MOD = 1e9 + 7;

int N, M, cnt = 0;
ll ans = 1;
char arr[2000][2000];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN2(N, M);
	FUP(i, 0, N - 1)
	{
		FUP(j, 0, M - 1)
		{
			CIN(arr[i][j]);
		}
	}

	FUP(i, 0, N - 1)
	{
		FUP(j, 0, M - 1)
		{
			int ok = 1;
			FUP(k, 0, 3)
			{
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
				if (arr[ny][nx] != arr[i][j])
				{
					ok = 0;
					break;
				}
			}
			cnt += ok;
		}
	}

	FUP(i, 1, cnt)
	{
		ans *= 2;
		ans %= MOD;
	}
	COUT(ans);

	return 0;
}