백준 14939번 불 끄기

문제 링크입니다: https://www.acmicpc.net/problem/14939

백준 14927번 전구 끄기(http://jaimemin.tistory.com/699)와 동일한 문제입니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int MAX = 10;

const int INF = 987654321;

 

int bulb[MAX];

int simulation[MAX];

 

//XOR를 이용해 전구 상태 바꿈

void pressSwitch(int y, int x)

{

        //자기 자신

        simulation[y] ^= (1 << (MAX - x - 1));

        //위

        if (y)

                 simulation[y - 1] ^= (1 << (MAX - x - 1));

        //아래

        if (y != MAX - 1)

                 simulation[y + 1] ^= (1 << (MAX - x - 1));

        //왼

        if (x)

                 simulation[y] ^= (1 << (MAX - x));

        //오

        if (x != MAX - 1)

                 simulation[y] ^= (1 << (MAX - x - 2));

}

 

int main(void)

{

        for (int i = 0; i < MAX; i++)

        {

                 string temp;

                 cin >> temp;

 

                 for (int j = MAX - 1; j >= 0; j--)

                         if (temp[j] == 'O')

                                 bulb[i] |= (1 << j);

        }

 

        int result = INF;

        //첫 row 2 ^ 10의 경우 모두 확인

        for (int candidate = (1 << MAX) - 1; candidate >= 0; candidate--)

        {

                 int press = 0;

                 for (int i = 0; i < MAX; i++)

                         simulation[i] = bulb[i];

 

                 //첫 x 2 ^ N의 경우 모두 확인

                 for(int x=0; x<MAX; x++)

                         if (candidate & (1 << x))

                         {

                                 pressSwitch(0, x);

                                 press++;

                         }

                 //이후에 (y - 1)행들의 전구를 다 끄기 위해

                 for(int y=1; y<MAX; y++)

                         for(int x=0; x<MAX; x++)

                                 if (simulation[y - 1] & (1 << (MAX - x - 1)))

                                 {

                                          pressSwitch(y, x);

                                          press++;

                                 }

                 //(MAX - 2)행까지의 전구를 모두 껐으므로 (MAX - 1) 행의 전구들이 다 꺼져있으므로

                 if (simulation[MAX - 1] == 0)

                         result = min(result, press);

        }

 

        if (result == INF)

                 cout << -1 << endl;

        else

                 cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~