백준 14939번 불 끄기 C++

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

 

처음 풀어보는 플래티넘 등급의 문제이다.

 

푸는 방법을 생각해내는 게 쉽지 않았다.

 

첫 번째 줄의 전구를 누르거나 누르지 않는 모든 경우 : 2^10 = 1024 이 경우들에서 시작하여 다음 줄에서부터는 

자신의 위쪽이 켜져 있으면 끄고, 아니면 넘어간다.  <- 이 방식으로 문제를 해결하였다.

 

이렇게 푸는 게 가능한 이유는

 

첫째, 한 스위치를 두 번 누르면 다시 원상태로 돌아가기 때문에 각 스위치는 최대 한 번만 누르면 된다. 

 

둘째, 1번 스위치를 누르고 2번 스위치를 누르는 것과, 2번 스위치를 누르고 1번 스위치를 누르는 것의 결과가 같다. 즉, 누르는 순서는 상관이 없다.

 

각 스위치는 최대 한 번만 누르면 되고, 누르는 순서는 상관이 없기 때문에 첫째줄에서 나온 각각의 경우들에 대해 2번째 줄부터 순차적으로 마지막 줄까지 탐색하면 된다.

 

푸는 방법을 생각하는 것은 쉽지 않았지만, 막상 코드를 짜는 것은 어렵지 않았던 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

vector<vector<bool>> board(10, vector<bool>(10));
vector<int> push;
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
int ans = 987654321;

void Push_Switch(int row, int col, vector<vector<bool>>& tmp_board) {
	tmp_board[row][col] = !tmp_board[row][col];
	for (int i = 0; i < 4; i++) {
		int nextRow = row + dRow[i];
		int nextCol = col + dCol[i];
		if (nextRow < 0 || nextRow >= 10) continue;
		if (nextCol < 0 || nextCol >= 10) continue;
		tmp_board[nextRow][nextCol] = !tmp_board[nextRow][nextCol];
	}
}

void BT(int idx) {
	if (idx > 9) {
		bool isAns = true;
		int cnt = 0;
		vector<vector<bool>> tmp_board(10, vector<bool>(10));
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				tmp_board[i][j] = board[i][j];
			}
		}
		for (auto a : push) {
			cnt++;
			Push_Switch(0, a, tmp_board);
		}
		for (int i = 1; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (tmp_board[i - 1][j]) {
					cnt++;
					Push_Switch(i, j, tmp_board);
				}
			}
		}
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (tmp_board[i][j]) isAns = false;
			}
		}
		if (isAns) {
			ans = min(ans, cnt);
		}
		return;
	}
	for (int i = idx; i <= 10; i++) {
		if (i == 10) {
			BT(i + 1);
		}
		else {
			push.push_back(i);
			BT(i + 1);
			push.pop_back();
		}
	}
}

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

	string str;
	for (int i = 0; i < 10; i++) {
		cin >> str;
		for (int j = 0; j < 10; j++) {
			if (str[j] == '#') board[i][j] = false;
			else board[i][j] = true;
		}
	}
	BT(0);
	cout << ans;
};