백준 14927번 전구 끄기

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

ssangba55(https://blog.naver.com/pasdfq/221206211990)님의 풀이를 보고 푼 문제입니다.

알고리즘은 아래와 같습니다.

1. 첫 행의 경우 모든 경우의 수를 고려해줍니다.(2^N가지의 전구 상태)

2. 두 번째 행부터 바로 위 행의 전구를 끄도록 스위치를 누릅니다.

3. 위와 같이 진행할 경우 1~(N-1)행의 전구는 모두 꺼져있습니다. 따라서 마지막 행의 전구가 모두 꺼져 있을 경우 모든 전구가 꺼져있다고 할 수 있습니다.

전구의 상태를 쉽게 표현하기 위해 행에 대해 일차원 배열로 선언하고 각 행의 상태를 비트마스킹을 통해 표현했습니다.

전구를 끄는 pressSwitch 함수는 쉽게 구현하기 위해 XOR을 이용하여 전구를 끄고 켰습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 18;

const int INF = 987654321;

 

int N;

int bulb[MAX];

int simulation[MAX];

 

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

void pressSwitch(int y, int x)

{

        //자기 자신

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

        //위

        if (y)

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

        //아래

        if (y != N - 1)

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

        //왼

        if (x)

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

        //오

        if (x != N - 1)

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

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

        cin >> N;

 

        //각 행을 비트로 입력

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

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

                 {

                         int temp;

                         cin >> temp;

                        

                         if (temp)

                                 bulb[i] |= 1 << j;

                 }

 

        int result = INF;

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

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

        {

                 int press = 0;

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

                         simulation[i] = bulb[i];

 

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

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

                         if (candidate&(1 << x))

                         {

                                 pressSwitch(0, x);

                                 press++;

                         }

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

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

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

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

                                 {

                                          pressSwitch(y, x);

                                          press++;

                                 }

                 //N-2행까지의 전구를 모두 껐으므로 N-1행의 전구들이 다 꺼져있으면 전부 꺼져있다.

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

                         result = min(result, press);

        }

 

        if (result == INF)

                 cout << -1 << endl;

        else

                 cout << result << endl;

 

        return 0;

}

 

개발환경:Visual Studio 2017

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