[백준/BOJ] 백준 14939번 : 불 끄기

www.acmicpc.net/problem/14939

14939번: 불 끄기

전구 끄기 문제로, 첫 행은 해당 위치를 눌렀을 때와 누르지 않았을 때 두 가지를 고려하고, 다음행부터 해당행의 윗행을 끄는 것에 맞춰서 전구를 누르거나 누르지 않는다. 그리고 모든 칸을 체크했을 때, 마지막행을 제외한 나머지행은 불이 꺼져 있다는 것이 보장되므로 마지막행만 확인하여 불이 꺼져있는지 확인한다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
using namespace std;

int board[10][10];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int result = 987654321;

void Push(pair<int, int> here)
{
	board[here.first][here.second] *= (-1);

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < 10 && there.second >= 0 && there.second < 10)
		{
			board[there.first][there.second] *= (-1);
		}
	}

}

void Solve(pair<int, int> here, int cnt)
{
	if (here.second == 10)
	{
		//모든 칸을 체크 했을때
		if (here.first == 9)
		{
			//마지막행 확인
			for (int i = 0; i < 10; i++)
			{
				if (board[9][i] == 1) //켜져 있는게 있을때
					return;
			}

			result = min(result, cnt);

			return;
		}

		else
			here = make_pair(here.first + 1, 0);
	}

	//첫 행일때
	if (here.first == 0)
	{
		//해당 위치를 누르지 않았을때
		Solve(make_pair(here.first, here.second + 1), cnt);

		//해당 위치를 눌렀을때
		Push(here);
		Solve(make_pair(here.first, here.second + 1), cnt + 1);
		Push(here);//원상복구
	}

	else
	{
		if (board[here.first - 1][here.second] == -1) //위에가 꺼진 전구일때
			Solve(make_pair(here.first, here.second + 1), cnt); //전구를 누르지 않고 넘어간다

		else //위에가 켜진 전구일때
		{
			Push(here); //전구를 누른다
			Solve(make_pair(here.first, here.second + 1), cnt + 1);
			Push(here); //원상 복구
		}
	}
}


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

	for (int i = 0; i < 10; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < input.size(); j++)
		{
			if (input[j] == '#')
				board[i][j] = -1;
			else
				board[i][j] = 1;
		}
	}

	Solve(make_pair(0, 0), 0);

	if (result == 987654321)
		cout << -1;
	else
		cout << result;

	return 0;
}