#14939: 불 끄기 (w/ Bit Masking)

14939번: 불 끄기

문제:

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라

입력:

10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.

풀이:

출처: https://technicolour.tistory.com/19

이 문제는 너무 여러워 위 출처에서 풀이 방법을 보며 풀었다. 친절히 설명 되어 있으니 시간이 된다면 위 출처를 확인 해 보길 바란다. 아래 풀이는 위 풀이를 내 방식으로 정리 해 놓은 풀이다.

브루트 포스 방식으로 모든 자리를 껐다 켜보는 방식을 생각 할 수 있지만 그러면 경우의 수는 2^100이므로 시간을 무조건 초과한다.

여기서 위의 출처에서 기발한 생각을 가르쳐 주는데 바로 첫번째 줄만 확인 하면 된다는 것이다.

왜나하면 어짜피 첫번째 줄에서 꺼저 있는 불을 켜버리면 아래줄에 가서 다시 버튼을 눌러 꺼줘야 된다는 기발한 아이디어인 것이다. 아래 그림을 보면 이해가 쉬울 것이다.

출처: https://technicolour.tistory.com/19

우선 구현을 하기 앞서 이 문제는 두가지 방법으로 풀 수 있다. 직접 배열하여 푸는 방법과 비트마스킹을 사용하는 방법이다.

🔎여기서 비트 마스킹이란 정수를 이진수 표현을 활요한 기법이다. 정수에 비트(이진수) 가면(마스크)를 씨운다고 생각하면 기억하기 쉬울 것이다. 관련 연산은 https://boycoding.tistory.com/163 이 출처를 보면 쉽게 이해 될 것이다.

구현:

1. char 입력 데이터를 bool로 저장해 준다.
2. 첫번째 줄의 껐다 키는 모든 경우의 수를 구한다 - 여기서 직접 배열 방식과 비트 마스킹 방식이 차이가 있다.
3. 첫번째 줄의 경우의 수에 따라서 위에서 말한 방법으로 나머지 줄을 자동으로 꺼주는 것이다. - 현재 for loop의 윗 줄에 불이 켜져있다면 그 아랫칸에 불을 꺼주는 방식으로 구현하면 된다.
4. 마지막으로 정렬내에 모든 불이 꺼졌나 확인하고 꺼젔다면 전에 나왔던 답과 비교하여 최소 값을 저장하면 된다.

코드(직접 배열):

#include <iostream>

using namespace std;

bool original[10][10];
int answer = 1e9;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void toggle(int x, int y, bool test_array[10][10]){
	for(int i = 0; i < 4; i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		//if not out of range
		if(!(nx < 0 || nx >= 10 || ny < 0 || ny >= 10)) test_array[nx][ny] = !test_array[nx][ny];
	}
	test_array[x][y] = !test_array[x][y];
}

bool alloff(bool array[10][10]){
	for (int i = 0; i < 10; i++){
		for (int j = 0; j < 10; j++){
			if(array[i][j]) return false;
		}
	}
	return true;
}

void copy(bool array1[10][10], bool array2[10][10], bool array[10][10]){
	for(int i = 0; i<10; i++){
		for(int j = 0; j<10; j++){
			array1[i][j] = array[i][j];
			array2[i][j] = array[i][j];
		}
	}
}

void brute_force(int x, int sum, bool array[10][10]){
	//after checking all possible combination for first line
	if(x == 10){
		bool test_array3[10][10] = {0, };
		for(int i = 0; i<10; i++){
			for(int j = 0; j<10; j++){
				test_array3[i][j] = array[i][j];
			}
		}
		//toggle for all lines after first line 
		for(int i = 1; i < 10; i++){
			for(int j = 0; j < 10; j++){
				if(test_array3[i-1][j]){
					toggle(i,j, test_array3);
					sum++;
				}
			}
		}
		if(alloff(test_array3)) answer = min(answer, sum);
		return;
	}
	
	bool test_array1[10][10], test_array2[10][10] = {0, };
	copy(test_array1, test_array2, array);
	
	//when not pressing
	brute_force(x+1, sum, test_array1);
	
	//when pressing
	toggle(0, x, test_array2);
	brute_force(x+1, sum+1, test_array2);
	
}

int main(void){
	
	for(int i = 0; i<10; i++){
		for(int j = 0; j<10; j++){
			char c;
			cin >> c;
			if(c=='O'){
				original[i][j] = 1;
			}
		}
	}
	
	brute_force(0, 0, original);
	
	if(answer == 1e9) cout << -1;
	else cout << answer;
	
}

코드(비트 마스킹):

#include <iostream>

using namespace std;

bool original[10][10], test[10][10];
int answer = 1e9;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,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 not out of range
		if(!(nx < 0 || nx >= 10 || ny < 0 || ny >= 10)) test[nx][ny] = !test[nx][ny];
	}
	test[x][y] = !test[x][y];
}

bool alloff(){
	for (int i = 0; i < 10; i++){
		for (int j = 0; j < 10; j++){
			if(test[i][j]) return false;
		}
	}
	return true;
}

void init_array(){
	for(int i = 0; i<10; i++){
		for(int j = 0; j<10; j++){
			test[i][j] = original[i][j];
		}
	}
}

void brute_force(){
	//Goes up till 2^10 which is all possible combination for the first line
	for(int step = 0; step < (1 << 10); step++){
		//step = combination of first line
		int counter = 0;
		init_array();
		//check if the light is on for the "step" 
		for(int bit = 0; bit < 10; bit++){
			//check if there are any lights on in "step"
			if(step & (1 << bit)){
				counter++;
				toggle(0, bit);
			}
		}
		for(int x = 1; x < 10; x++){
			for(int y = 0; y < 10; y++){
				if(test[x-1][y]){
					toggle(x,y);
					counter++;
				}
			}
		}
		if(alloff()) answer = min(counter, answer);
	}
}

int main(void){
	
	for(int i = 0; i<10; i++){
		for(int j = 0; j<10; j++){
			char c;
			cin >> c;
			if(c=='O'){
				original[i][j] = 1;
			}
		}
	}
	
	brute_force();
	
	if(answer == 1e9) cout << -1;
	else cout << answer;
	
}