BOJ 14939 - 전구 끄기 (비트마스크, 그리디, 완탐)

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

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

 

<문제설명>

n*n그리드 위에 꺼진전구와 켜진 전구가 주어진다. 한 전구의 스위치를 누르면 주변4방향과 자기 자신의 상태가 변한다. 모든 전구를 끄기위해 최소 몇번 스위치를 눌러야 하는가?

(n<=18)

 

<풀이>

한 위치의 스위치를 두번 이상 누르는 경우는 없다.

 

맨 윗줄의 스위치를 누르는 경우의 수는 (1<<n)가지가 있다. 각각의 경우마다 그 아랫줄의 스위치를 누르는 경우는 단 한가지로 정해진다.

 

모든 줄의 스위치를 적절히 누른 후, 맨 밑줄의 상태가 모두 꺼져있다면 가능, 그외 불가능

 

<코드>

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

bool a[20][20], flag;
int b[20][20], n, cnt;

void clr(int i, int j) {
	cnt++;
	for (int k = 0; k < 5; k++) b[i + dy[k]][j + dx[k]]++;
}

int main() {
	FAST; cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];

	int ans = 1e9;
	for (int x = 0; x < (1 << n); x++) {
		memset(b, 0, sizeof(b));
		flag = cnt = 0;
		for (int i = 0; i < n; i++)
			if (x & (1 << i)) clr(1, i + 1);

		for (int i = 2; i <= n; i++) for (int j = 1; j <= n; j++) {
			if (a[i - 1][j] && b[i - 1][j] % 2 == 0) clr(i, j);
			if (!a[i - 1][j] && b[i - 1][j] % 2 == 1) clr(i, j);
		}
		for (int j = 1; j <= n; j++) {		
			if (a[n][j] && b[n][j] % 2 == 0) flag = true;
			if (!a[n][j] && b[n][j] % 2 == 1) flag = true;		
		}
		
		if (!flag) ans = min(ans, cnt);
	}
	
	cout << (ans == 1e9 ? -1 : ans) << '\n';
}