카카오 코드 페스티벌 2018 본선 문제 풀이 - 뒤집기

제출자: 61

정답자: 60

정답률: 98.4%

문제: https://www.acmicpc.net/problem/15999

15999번: 뒤집기

풀이

문제를 조금만 관찰하면 금방 패턴을 파악할 수 있는 문제입니다.

현재 상태가 주어졌을 때 초기 상태로 가능한 경우를 생각해보면 바로 풀리는 문제입니다.

 

예를 들어 현재 상태가 WB였을 때, 초기상태로 가능한 것은 WW, BB, WB, BW중 하나 이상일 것입니다.

 

WW는 WB가 될 수 없으므로 초기상태가 불가능합니다.

BB또한 WB가 될 수 없습니다.

WB는 WB에서 0번 건들면 현재 상태가 됩니다.

BW는 WB가 되려면 B를 누르거나 W를 눌러야하는데, 그렇게되면 WW혹은 BB가 됩니다. 따라서 WB가 될 수 없습니다.

 

결론은 서로 인접한 격자가 다른 타일이라면 초기상태와 현재상태는 같다 입니다.

그 외의 격자들은 초기상태가 어떻든 현재상태로 만들 수 있습니다.

 

WW는 WW, BB, WB, BW 모두 초기상태가 가능합니다. 총 4가지 경우의 수 입니다.

 

WWB는 WWB, BWB가 가능합니다. 총 2가지 경우의 수 입니다.

 

즉, 어떤 타일에 대해서 상하좌우 모두 자신과 같은 색의 타일 (혹은 벽)이라면, 그 타일은 W이든 B이든 상관이 없다는 결론이 나옵니다. 이경우를 고립 타일 이라고 정의하겠습니다.

 

따라서 정답은 \(2^(\hbox{고립 타일})\)입니다.

 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

#define DIV 1000000007

int N, M;
int board[2000][2000];

bool isIsolated(int r, int c) {
	int delta[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
	int a = 0;
	for (int i = 0; i < 4; i++) {
		int dr = r + delta[i][0];
		int dc = c + delta[i][1];
		if (dc >= 0 && dc < M && dr >= 0 && dr < N) {
			if (board[r][c] == board[dr][dc])
				a++;
			else
				return false;
		}
		else
			a++;
	}
	return (a == 4) ? true : false;
}

int exp2(int n) {
	if (n == 0)
		return 1;
	int ret = exp2(n - 1);
	return (ret * 2) % DIV;
}

int solve() {
	int n = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (isIsolated(i, j))
				n++;
	return exp2(n);
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		char s[2001] = { 0 };
		scanf("%s", s);
		for (int j = 0; j < M; j++) // W = 0, B = 1
			board[i][j] = s[j] == 'W' ? 0 : 1;
	}
	printf("%d", solve());

}

 

이해되지 않는 부분이 있으시면 댓글 남겨주시면 됩니다.