[백준/BOJ] 백준 14927번 : 전구 끄기

www.acmicpc.net/problem/14927

14927번: 전구 끄기

전구 문제로서, 첫 행일 때는 현재 위치를 클릭하는 경우와 클릭하지 않는 경우를 모두 고려하고, 다음행부터 위에 행의 위치가 꺼져야 하는 것을 판단으로 클릭할지, 클릭하지 말지 선택을 한다. 그리고 마지막에는, 마지막행을 제외한 나머지 행들은 모두 전구가 꺼져 있는 것이 보장되어 있으므로 마지막 행만 확인하여 마지막 행이 모두 꺼져 있는지 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int board[18][18];
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 < n && there.second >= 0 && there.second < n)
			board[there.first][there.second] *= (-1);
	}
}

//마지막 행을 확인
bool Check()
{
	for (int j = 0; j < n; j++)
	{
		if (board[n - 1][j] == 1) //켜져있는 전구가 있을때
			return false;
	}

	return true;
}

void Solve(pair<int, int> here, int click)
{
	if (here.second == n)
	{
		if (here.first == n - 1)
		{
			if (Check()) //전구가 다 꺼졌다면
				result = min(result, click);

			return;
		}

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

	//첫 행일때
	if (here.first == 0)
	{
		//here를 클릭하지 않는 경우
		Solve(make_pair(here.first, here.second + 1), click);

		//here를 클릭하는 경우
		Push(here);
		Solve(make_pair(here.first, here.second + 1), click + 1);
		Push(here); //원상복구
	}

	else
	{
		if (board[here.first - 1][here.second] == -1) //here위가 꺼져 있을때
			Solve(make_pair(here.first, here.second + 1), click); //클릭하지 않고 넘아간다

		else //here위가 켜져 있을때
		{
			//클릭하고 넘어간다
			Push(here);
			Solve(make_pair(here.first, here.second + 1), click + 1);
			Push(here); //원상복구
		}
	}
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			if (input == 0)
				input = -1;

			board[i][j] = input;
		}

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

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

	else
		cout << result;

	return 0;
}