백준/14939번/불 끄기/플래티넘4

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

문제 설명

Site: Baekjoon
Number: 14939
Category: BruteForce
Rank: Platinum 4

10 x 10 배열에서 O가 켜진 전구로 주어졌을 때, 스위치를 누르면 해당 자리와 주위 4 방향 스위치를 끌 수 있습니다.

이 때, 스위치를 눌러 모든 전구를 끄는 최소 횟수를 구하는 문제입니다.

문제 풀이

BFS 또는 DFS로 스위치의 온오프 여부로 돈다면 해결할 수 없기 때문에 모든 경우의 수를 확인해봐야 합니다.

첫 줄 스위치를 누르는 모든 경우의 수를 파악하고, 2 ~ 10번째 줄은 윗 줄의 전구가 켜져있다면 해당 줄을 지나면 더 이상 끌 수 없기 때문에 스위치를 누릅니다.

모든 배열을 순회하고 마지막에 전구가 켜져있는지 확인한다음 최솟값을 갱신하는 방식을 사용하였습니다.

#include <iostream>
#include <vector>

#define INF 1000000000

using namespace std;

int dirx[5] = { 0, 0, -1, 0, 1 };
int diry[5] = { 0, -1, 0, 1, 0 };

vector<vector<bool>> bulbs(10, vector<bool>(10, false));
vector<vector<bool>> temp(10, vector<bool>(10, false));;


void Switch(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        int newx = x + dirx[i];
        int newy = y + diry[i];

        if (newx < 0 || newy < 0 || newx >= 10 || newy >= 10)
            continue;

        temp[newx][newy] = !temp[newx][newy];
    }
}

int Find(int num)
{
    int cnt = 0;

	for(int i = 0; i < 10 ;i++)
	{
        if (num & 1)
        {
            Switch(0, i);
            cnt++;
        }
        num = num >> 1;
	}

    for(int i = 1; i < 10; i++)
    {
	    for(int j = 0; j < 10; j++)
	    {
            if (temp[i - 1][j] == true)
            {
                Switch(i, j);
                cnt++;
            }
	    }
    }

    for(int i = 0; i < 10; i++)
    {
	    for(int j = 0; j < 10; j++)
	    {
            if (temp[i][j] == true)
                return INF;
	    }
    }

    return cnt;
}

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

    int ans = INF;

    for(int i = 0; i < 10; i++)
    {
	    for(int j = 0; j < 10; j++)
	    {
            char c;
            cin >> c;
            if (c == 'O')
                bulbs[i][j] = true;
	    }
    }

    for (int i = 0; i <= ((1 << 10) - 1); i++)`
	{
        temp = bulbs;
        ans = min(ans, Find(i));
	}

    cout << ((ans == INF) ? -1 : ans);

    return 0;
}