[백준] 14939.cpp : 불 끄기

www.acmicpc.net/problem/14939

14939번: 불 끄기

---

• 같은 버튼이 두 번 이상 눌리지 않는다. 그 순간 최솟값이 될 수가 없다.
• 모든 버튼이 한번씩만 눌린다고 했을 경우에는 각 버튼을 누르는 순서가 중요해지지 않는다.
• 그렇게 되면 위에서부터 한 줄씩 차례대로 내려오면서 검사하면 된다.
• 위에서부터 내려올 경우, 둘째 줄부터는 자신의 바로 윗줄의 상태에 따라서 누를지 말지 여부가 결정된다. 바로 윗칸의 버튼이 켜져 있는 상태라면 반드시 눌러서 꺼줘야 하고, 윗칸이 꺼져있으면 누르면 안되기 때문이다.
• 나머지 줄들은 윗줄의 상태에 의해 자동 결정되므로, 첫 줄의 상태만 고려하면 된다.
• 첫 줄에는 10칸이 있고, 각각 켜짐과 꺼짐의 상태가 있으므로 모든 경우의 수 1024 가지를 고려하여 계산하면 된다.

---

#include <iostream>

using namespace std;

int num = 1000;                 // 정답 넣어줄 변수, 이상치는 1000 으로 설정
bool state[10][10];             // 매번 검사해줄 용도의 배열
bool fixedState[10][10];        // 처음 입력받을 값들 고정 저장될 배열

void click(int row, int col)    // 해당 위치를 클릭했을 때 전구들의 상태를 바꿔줌
{
    state[row][col] = !state[row][col];
    if(row-1 >= 0) state[row-1][col] = !state[row-1][col];
    if(row+1 < 10) state[row+1][col] = !state[row+1][col];
    if(col-1 >= 0) state[row][col-1] = !state[row][col-1];
    if(col+1 < 10) state[row][col+1] = !state[row][col+1];
}

int check()                                         // state 배열이 유효한지, 유효하다면 클릭 수는 몇회인지 반환
{
    int temp = 0;
    for(int r = 1 ; r < 10 ; r++)                   // 첫 줄은 메인에서 처리됐으므로 두번째 줄부터 시작
    {
        for(int c = 0 ; c < 10 ; c++)
        {
            if(state[r-1][c])                       // 바로 윗 줄의 같은 칸의 전구가 켜져있는 상태면 무조건 눌러야 함
            {
                click(r, c);
                temp++;
            }
        }
    }
    for(int r = 0 ; r < 10 ; r++)                   // 쭉 검사했는데 켜져있는 전구가 있으면
    {
        for(int c = 0 ; c < 10 ; c++)
        {
            if(state[r][c] == true) return 1000;    // 불가능함, 1000 반환
        }
    }
    return temp;
}

int main(void)
{
    char temp;
    for(int r = 0 ; r < 10 ; r++)
    {
        for(int c = 0 ; c < 10 ; c++)
        {
            cin >> temp;
            if(temp == 'O') fixedState[r][c] = true;        // 처음에 정보 입력 받음
        }
    }
    for(int p = 0 ; p < 1024 ; p++)                         // 첫 줄 10개를 각각 킬지/끌지 에 대해서 모든 경우의 수 탐색
    {                                                       //  (2의 10승)
        for(int r = 0 ; r < 10 ; r++)
        {
            for(int c = 0 ; c < 10 ; c++)                   // 해당 반복문을 수행하기 위해 state 배열을 초기화
            {
                state[r][c] = fixedState[r][c];
            }
        }
        int ret = 0;
        for(int i = 0 ; i < 10 ; i++)                       // 비트마스킹을 통해 첫 줄 10개의 전구를 누를지 말지 판단
        {
            if(p & (1 << i))                                // 해당 전구를 눌러야 하는 위치라면
            {   
                ret++;                                      // 누름 처리
                click(0, i);
            }
        }
        ret += check();                                     // state 에 1024번 중 현재 반복(첫 줄 전구)의 상태 담겨있음
        if(ret < num) num = ret;                            // 최솟값 갱신
    }

    cout << (num == 1000 ? -1 : num) << '\n';               // 모든 경우의 수가 이상치 반환할 경우 불가능 -1 출력
}