백준 15999번: 뒤집기

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

15999번: 뒤집기

---

이 문제는 카카오 코드 페스티벌 2018이 출처이고, 카카오 테크 블로그에 간략한 증명과 해설이 나와 있습니다.

 

그대로 구현하면 정답을 받을 수 있습니다. ( 코드 페스티벌 2018 카카오 본선 이야기 )

 

전체적인 코드에서 그나마 주목할 만한 점은 한 칸에서 인접한 칸들의 상태를 검사해주는 부분입니다.

 

이 부분은 뭔가 더 최적화할 여지가 없을까 싶었는데 코드가 장황해서 잘 눈에 안 들어오고 쉽지 않네요.

 

예외 처리를 하는 부분만 본다면, 우선 $N=1$ 일 때와 $M=1$ 일 때에 초점을 맞췄습니다.

 

특히 $N=M=1$ 인 경우는, 항상 adjacent한 것으로 처리하여 답이 2가 나올 수 있도록 했습니다.

 

코드는 다음과 같습니다.

#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007

int check_adjacent(char** array, int N, int M, int i, int j);

long long power_modular (long long X, long long Y);

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	char** array = (char**)malloc(sizeof(char*) * N);
	for (int i = 0; i < N; i++) {
		array[i] = (char*)malloc(sizeof(char) * M);
	}
	
	for (int i = 0; i < N; i++) {
		scanf("%s", array[i]);
	}
	
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			count += check_adjacent(array, N, M, i, j);
		}
	}
	
	printf("%lld", power_modular(2, count));
	
	for (int i = 0; i < N; i++) {
		free(array[i]);
	}
	free(array);
	return 0;
}

int check_adjacent(char** array, int N, int M, int i, int j) {
	
	if (N == 1 && M == 1) {
		return 1;
	}
	
	if (N == 1) {
		if (j == M - 1) {
			if (array[i][j] == array[i][j-1]) {
				return 1;
			}
			return 0;
		}
		if (j == 0) {
			if (array[i][j] == array[i][j+1]) {
				return 1;
			}
			return 0;
		}
		if (array[i][j] == array[i][j+1] && array[i][j] == array[i][j-1]) {
			return 1;
		}
		return 0;
	}
	
	if (M == 1) {
		if (i == N - 1) {
			if (array[i][j] == array[i-1][j]) {
				return 1;
			}
			return 0;
		}
		if (i == 0) {
			if (array[i][j] == array[i+1][j]) {
				return 1;
			}
			return 0;
		}
		if (array[i][j] == array[i+1][j] && array[i][j] == array[i-1][j]) {
			return 1;
		}
		return 0;
	}
	
	if (i == 0) {
		if (j == 0) {
			if (array[i][j] == array[i+1][j] && array[i][j] == array[i][j+1]) {
				return 1;
			}
			return 0;
		}
		if (j == M - 1) {
			if (array[i][j] == array[i+1][j] && array[i][j] == array[i][j-1]) {
				return 1;
			}
			return 0;
		}
		if (array[i][j] == array[i+1][j] && array[i][j] == array[i][j+1] && array[i][j] == array[i][j-1]) {
			return 1;
		}
		return 0;
	}
	
	if (j == 0) {
		if (i == N - 1) {
			if (array[i][j] == array[i-1][j] && array[i][j] == array[i][j+1]) {
				return 1;
			}
			return 0;
		}
		if (array[i][j] == array[i-1][j] && array[i][j] == array[i+1][j] && array[i][j] == array[i][j+1]) {
			return 1;
		}
		return 0;
	}
	
	if (i == N - 1) {
		if (j == M - 1) {
			if (array[i][j] == array[i-1][j] && array[i][j] == array[i][j-1]) {
				return 1;
			}
			return 0;
		}
		if (array[i][j] == array[i-1][j] && array[i][j] == array[i][j-1] && array[i][j] == array[i][j+1]) {
			return 1;
		}
		return 0;
	}
	
	if (j == M - 1) {
		if (array[i][j] == array[i][j-1] && array[i][j] == array[i+1][j] && array[i][j] == array[i-1][j]) {
			return 1;
		}
		return 0;
	}
	
	if (array[i][j] == array[i][j+1] && array[i][j] == array[i][j-1] && array[i][j] == array[i+1][j] && array[i][j] == array[i-1][j]) {
		return 1;
	}
	return 0;
}

long long power_modular (long long X, long long Y) {
	long long answer = 1;
	while(Y) {
		if (Y % 2) {
			answer = answer * X % mod;
		}
		X = X * X % mod;
		Y /= 2;
	}
	return answer;
}

(C11, 4944KB, 84ms, 제출번호 28479342)

---

처음 문제를 보면 막히기 아주 쉬운 문제입니다.

 

특히 현재 상태가 BW일 때 초기 상태가 WB일 수 없다는 부분이 솔루션을 보고도 납득하기 어려웠던 것 같습니다.