[백준 14939] 불끄기

문제

www.acmicpc.net/problem/14939

14939번: 불 끄기

 

풀이

모든 전구의 상태를 완전탐색한다면 $O(2^n)$으로 시간초과가 나기 때문에 다른 방법을 생각해봐야 합니다.

 

문제에서 구하는건 최소한으로 누르는 스위치의 개수이기에 스위치를 누르는 횟수를 줄이기 위해서 같은 스위치를 2번이상 누르지 않도록 해야합니다.

---

1. 스위치를 누르는 방향을 정해놓고 전구를 순회하면 한 번 누른 스위치는 다시 누르는 경우가 생기지 않으므로 방향을 정해놓고 진행합니다. (아래의 풀이에선 좌측상단에서 우측하단으로 방향을 정했습니다.)

 

2. 어떤 방향으로 순회하던 첫 번째 줄은 다른 줄들과 다르게 스위치를 눌렀을 때 세 방향만 전구의 상태가 바뀌므로 첫 번째 줄의 스위치상태만 ((2^10)가지) 정해준다면 그 아랫 줄부터는 항상 윗줄의 전구가 켜져있을 때만 스위치를 꺼주는 식으로 맵 전체를 순회하면 됩니다. 

 

3. 위와 같은 방식으로 맵 전체를 순회했을 때, 마지막 줄을 제외한 나머지 줄에선 전구가 모두 꺼져있기 때문에 마지막 줄의 전구가 켜져있는지만 확인하면 모든 전구가 꺼졌는지 확인할 수 있습니다.   

 

코드

#include <bits/stdc++.h>
using namespace std;
 
const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int ans, nr, nc, cnt;
string tmp[10];
bool g[11][11], G[11][11], flag;
 
void toggle(int r, int c) {
	g[r][c] ^= 1;
	for (int i = 0; i < 4; i++) {
		nr = r + dir[i][0], nc = c + dir[i][1];
		if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10) continue;
		g[nr][nc] ^= 1;
	}
}
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	ans = 1e9;
	for (int i = 0; i < 10; i++) {
		cin >> tmp[i];
		for (int j = 0; j < 10; j++)
			g[i][j] = (tmp[i][j] == '#' ? 0 : 1);
	}
	for (int i = 0; i < (1 << 10); i++) {
		cnt = flag = 0;
		memcpy(G, g, sizeof(g));
		for (int j = 0; j < 10; j++)
			if (i & (1 << j))
				toggle(0, j), cnt++;
		for (int j = 1; j < 10; j++)
			for (int k = 0; k < 10; k++)
				if (g[j - 1][k])
					toggle(j, k), cnt++;
		for (int j = 0; j < 10; j++)
			if (g[9][j]) 
				flag = 1;
		ans = (flag == 0 ? min(ans, cnt) : ans);
		memcpy(g, G, sizeof(g));
	}
	cout << (ans == 1e9 ? -1 : ans);
}