[백준 14939] 불 끄기

백준 14939번 : 불 끄기

www.acmicpc.net/problem/2170

2170번: 선 긋기

 

---

/* 문제 설명 */

전구 켜져 있다 == 1, 꺼져 있다 == 0

10×10 배열이 있을 때, 한 칸을 누르면 그 위치에서 위, 아래, 왼쪽, 오른쪽에 있는 배열의 상태가 바뀌게 된다.

모든 배열을 0으로 만들기 위해서는 최소 몇 번 눌러야 하는가?

 

 

/* 해결 방안 */

 

가로가 10칸이고, 세로가 10칸 이므로, 총 100칸에 대해서 클릭할지 말지를 선택해야 된다.

따라서 경우의 수가 총 2^100이므로, 브루트 포스를 이용할 경우 시간 초과가 나게 된다.

 

그렇다면, 어떻게 시간을 줄여야 할까? 잘 생각해보면, 두 가지 규칙이 보인다.

 

1) 한 번 누른 칸은 다시 누를 필요가 없다.

    예를 들자면, (0, 0) 칸을 눌러서 불을 껐는데, (0, 0) 칸을 또 누르면 다시 불이 켜지게 된다.

    따라서 당연한 소리겠지만, 같은 칸을 두 번 클릭 할 필요가 없다

 

2) 어떤 순서로 누르든 상관이 없다

    즉, (0,0)→ (1,1) 이나 , (1,1) → (0,0) 이나 결과는 똑같다는 뜻이다.

 

1번과 2번 생각을 통해, 우리는 '아, 그럼 for문을 통해 첫 줄부터 마지막 줄 까지 버튼을 누를지 말지를 정하면 되겠구나!'라고 생각 할 수 있다.

 

 

이런 당연한 생각으로 문제를 도대체 어떻게 풀까??

일단 첫 줄부터 차근차근 눌러주자!

 

만약 첫 줄부터 탐색 했을 때 하늘색 칸에 대해 불을 켜줬다면, 두 번째 줄에서는 어떻게 행동 해야할까?

우리는 for문을 차례대로 돌고 있어서, 위나 왼쪽으로는 돌아갈 수 없는 상황이다.

 

따라서 두 번째 줄에서 '첫 번째 줄에서 무조건 켜져있는 칸'을 꺼주고 가야된다.

(왜냐면, 세 번째 줄으로 내려가는 순간 첫 번째 줄에 대해 건들 수 없기 때문이다)

→ 따라서 초록색 칸에 대해 클릭을 해서 하늘색 애들을 꺼줘야 한다.

 

이를 통해, 첫 번째 줄을 어떻게 하느냐에 따라서 나머지 줄들의 클릭이 결정 됨을 알 수 있다.

 

따라서 첫 번째 줄에 대해서만 완전 탐색을 해주면 된다.
한 줄에 10칸이므로, 2^10 번에 대해서만 탐색을 해주면 되고, 이는 시간 제한 안에 충분히 수행할 수 있다.

 

 

/* 구현 과정 */

1. 우선 구현을 편하게 하기 위해서, 불이 켜져있는 곳은 true로, 꺼져있는 곳은 false로 바꿔준다.

2. 첫 번째 줄에 대해서 모든 경우의 수를 구해준다.

3. 각 경우의 수 마다, 두 번째 줄~ 마지막 줄까지 for문을 돌면서 불을 켤지 말지를 처리 해준다.

4. 위의 for문을 돌았다면, 모든 전구가 꺼져있는지 확인하고, 만약 모든 전구가 꺼져있다면, ans=min(ans, cnt)를 통해 정답을 구한다. 

 

 

/* 소스 코드 */

여기서 풀이 방법은 두 가지가 있다.

하나는 구현을 쉽게 하기 위해 비트마스킹을 쓰는 것이고,

다른 하나는 비트마스킹을 모르는 경우, 직접 배열을 넘겨가며 풀면 된다.

 

우선 비트마스킹 풀이 먼저 보자!

 

1) 비트 마스킹

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 10
#define INF 1e9

bool arr[15][15], tmp_arr[15][15];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans = INF;

bool outrange(int x, int y) {
	if (x < 0 || x >= MAX || y < 0 || y >= MAX) return 1;
	return 0;
}

//전구를 클릭 했을 때 이벤트 처리
void toggle(int x, int y) {
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (!outrange(nx, ny)) tmp_arr[nx][ny] = !tmp_arr[nx][ny];
	}
	tmp_arr[x][y] = !tmp_arr[x][y];
}

//기존 배열을 건들면 안되므로, 임시 배열에 값을 복사해준다.
void init() {
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			tmp_arr[i][j] = arr[i][j];
}

//불이 켜져있는지 확인한다
bool islight() {
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			if (tmp_arr[i][j]) return 1;
	return 0;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

		//불이 켜져있는 경우 true를 넣어준다.
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++)
		{
			char c; cin >> c;
			if (c == 'O') arr[i][j] = 1;
		}
	}

	//첫 번째 줄이 가질 수 있는 모든 경우의 수(2^10)에 대해 탐색한다.
	for (int step = 0; step < (1<< MAX); step++)
	{
		int cnt = 0;
        	//매 step마다 배열을 원상 복구 해줘야 한다.
		init();

		//step에는 1101100011 이렇게 몇 번째 칸에 대해서 클릭 할 지가 적혀있다.
        
		for (int bit = 0; bit < MAX; bit++)
		{
        		//첫 번째 줄의 bit 번 째 칸의 줄이 켜져있고, step을 봤을 때 이 칸을 클릭할 수 있는지 확인한다.
			if (step & (1 << bit)) {
				cnt++;
				toggle(0, bit);
			}
		}

			//첫 번째 줄에 대한 처리가 끝났으므로, 두 번째 줄 ~ 마지막 줄을 탐색한다.
		for (int x = 1; x < MAX; x++)
		{
			for (int y = 0; y < MAX; y++)
			{
				if (tmp_arr[x - 1][y]) {
					toggle(x, y);
					cnt++;
				}
			}
		}
        
        	//불이 모두 꺼져 있다면, ans의 최솟값을 갱신한다.
		if (!islight()) ans = min(cnt, ans);
	}

		//초기에 ans에 말도 안되게 큰 값(INF)을 넣어줬는데, 여전히 INF라면 단 한 번도 불이 모두 꺼진 적이 없다는 뜻이므로 -1을 출력한다.
	if (ans == INF) cout << -1;
	else cout << ans;
}

 

 

 

2) 비트마스킹을 사용하지 않는 풀이

 

맨 처음에 이 문제를 풀었을 때, 비트마스킹을 전혀 떠오르지 못했다.

그래서 빡구현(...)으로 직접 배열을 넘겨가며 풀 생각을 하고 있었는데, 많은 분들이 tag에 비트마스킹을 다셨길래 위에 처럼 풀었다.

 

근데 비트마스킹을 모르는 친구에게 설명해줄 일이 있어서 빡구현 방식으로 마저 풀었다.

 

여기서 중요한 점은 c++ 특성 상, 배열을 매개변수로 넣어주면 주소가 넘어가서 함수를 수행하면 원 배열의 값이 달라진다는 점이다.

 

따라서 매 함수의 시행마다, tmp 배열에 다가 copy를 해줘야 한다.

이것말고는 구현 과정은 똑같다.

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 10
#define INF 1e9

bool arr[15][15];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans = INF;

bool outrange(int x, int y) {
	if (x < 0 || x >= MAX || y < 0 || y >= MAX) return 1;
	return 0;
}

void toggle(int x, int y, bool tmp_arr[][15]) {
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (!outrange(nx, ny)) tmp_arr[nx][ny] = !tmp_arr[nx][ny];
	}
	tmp_arr[x][y] = !tmp_arr[x][y];
}


bool islight(bool tmp_arr[][15]) {
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			if (tmp_arr[i][j]) return 1;
	return 0;
}

void init(bool t_arr1[][15], bool t_arr2[][15], bool t_arr[][15]) {
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++) {
			t_arr2[i][j] = t_arr[i][j];
			t_arr1[i][j] = t_arr[i][j];
		}
}

void firstLine(int x, int sum, bool t_arr[][15]) {
	if (x == MAX) {
		//copy
		bool t_arr3[15][15] = { 0, };
		for (int i = 0; i < MAX; i++)
			for (int j = 0; j < MAX; j++)
				t_arr3[i][j] = t_arr[i][j];


		//두 번째 ~ 마지막 줄에 대해서 toggle 진행
		for (int i = 1; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				if (t_arr3[i - 1][j]) {
					toggle(i, j, t_arr3);
					sum++;
				}
			}
		}
		
		//모든 불이 다 꺼져 있으면!
		if (!islight(t_arr3))  ans = min(ans, sum);
		return;
	}

	bool t_arr1[15][15] = { 0, };
	bool t_arr2[15][15] = { 0, };

	//c++ 특성상, 배열의 주소를 넘겨주므로 새로운 함수를 만날 때 마다
	//원 배열의 값이 달라진다. 따라서 계속 copy를 해줘야 됨
	init(t_arr1, t_arr2, t_arr);

	//해당 칸을 안누르고 넘어가는 경우
	firstLine(x + 1, sum, t_arr1);

	//해당 칸을 누르고 넘어가는 경우
	toggle(0, x, t_arr2);
	firstLine(x + 1, sum + 1, t_arr2);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++)
		{
			char c; cin >> c;
			if (c == 'O') arr[i][j] = 1;
		}
	}

	firstLine(0, 0, arr);

	if (ans == INF) cout << -1;
	else cout << ans;
}

/* 얻어갈 점 */

1. c++에서 2차원 배열을 넘겨 줄 때는 int func(bool arr[][15]) 이렇게 마지막에는 배열의 크기를 지정해줘야한다.

1차원 배열이라면, 그냥 int func(bool arr[]) 이렇게 하자! 

둘 다 함수를 호출 할 때는 func(arr) 처럼 이름만 넣어주면 된다.

 

2. 지금까지 비트 마스킹은 TSP같은 문제에 대해서 방문체크를 해줄 때 쓰는 거 라고만 생각했고, 그래서 모두 함수(dfs 과정)를 통해서 접근해야된다고 생각했다.

이렇게 반복문을 통해서도 사용할 수 있다는 점과 꽤 작은 경우의 수를 따져할 때 비트마스킹을 의심해봐야겠다.

 

 

 

 

---