[Algorithm]Baekjoon 14939 :: 불 끄기

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

14939번: 불 끄기

 
 
using namespace std;
 
 
char arr[10][10];
char temp[10][10];
int answer = 0x3f3f3f3f;
 
void switchOn(int row, int col, bool isTemp)
{
    if (isTemp == false)
    {
        arr[row][col] = arr[row][col] == 'O' ? '#' : 'O';
 
        if (row - 1 >= 0) arr[row - 1][col] = arr[row - 1][col] == 'O' ? '#' : 'O';
        if (row + 1 < 10) arr[row + 1][col] = arr[row + 1][col] == 'O' ? '#' : 'O';
        if (col - 1 >= 0) arr[row][col - 1] = arr[row][col - 1] == 'O' ? '#' : 'O';
        if (col + 1 < 10) arr[row][col + 1] = arr[row][col + 1] == 'O' ? '#' : 'O';
    }
    else
    {
        temp[row][col] = temp[row][col] == 'O' ? '#' : 'O';
 
        if (row - 1 >= 0) temp[row - 1][col] = temp[row - 1][col] == 'O' ? '#' : 'O';
        if (row + 1 < 10) temp[row + 1][col] = temp[row + 1][col] == 'O' ? '#' : 'O';
        if (col - 1 >= 0) temp[row][col - 1] = temp[row][col - 1] == 'O' ? '#' : 'O';
        if (col + 1 < 10) temp[row][col + 1] = temp[row][col + 1] == 'O' ? '#' : 'O';
    }
}
 
void allSwitchOn(int count)
{
    memcpy(temp, arr, sizeof(temp));
 
    for (int i = 1; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if (temp[i - 1][j] == 'O') // 바로 윗행께 켜져있으면
            {
                ++count;
                switchOn(i, j, true);
            }
        }
    }
 
    for (int i = 0; i < 10; ++i)
    {
        if (temp[9][i] == 'O') return; // 하나라도 켜져있으면 그냥 종료.
    }
 
    answer = min(answer, count);
}
 
 
void DFS(int columnIndex, int count)
{
    if (columnIndex == 10)
    {
        allSwitchOn(count);
        return;
    }
 
    DFS(columnIndex + 1, count); // 안누르고 넘어가거나
    switchOn(0, columnIndex, false); // 누르고,
    DFS(columnIndex + 1, count+1); // 넘어간다.
    switchOn(0, columnIndex, false); // 다시 되돌려줘야 한다.
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    DFS(0,0);
 
    if (answer == 0x3f3f3f3f)
    {
        cout << -1;
    }
    else cout << answer;
}

 

백준 2138번문제인 전구와 스위치에서 1차원 더 확장된 문제이다.

만약 전구와스위치 문제를 잘 이해했더라면 무조건 바로 이해할 수 있다.

 

초기에 상태가 주어졌을 때, 최소한의 스위치조작으로 타겟상태로 만들어야하는 문제이다.

단순하게 브루트포스로생각해서 모든 경우의 수를 따지면 2^100이기 때문에 당연히 안된다.

그래서 첫행의 요소들만 키고 끄는 탐색을 진행해준다. 

그러면 이후 2번째행~9번째 행에 대해서는 켜야할지, 꺼야할지가 정해진다..! 

 

두번째행부터 각 열을 돌면서 스위치를 조작할것인지, 안할것인지 결정할건데 그 기준은 바로 윗행의 원소 (arr[i-1][j])가 켜져있으면 스위치를 조작하고 꺼져있으면 조작하지 않는다.

왜냐하면 현재에서(arr[i][j])에서 조작을 안하고 넘어가면, 이후에는 arr[i-1][j]의 값을 바꿀수가 없다. 반드시 모든 전구를 다 꺼야하기 때문에 지금 조작을 할지 안할지 결정해야하며, 그렇기 때문에 여기서 다시 두개의 재귀탐색으로 갈라지지 않는것이다.

 

9번째 행까지 전부 진행한 후, 반복문으로 10번째 행의 열들만 돌면서 만약 전구가 하나라도 켜져있을 경우, 더이상 조작할 수 없기 때문에 타겟상태(전구가 전부 꺼져있는)로 만들 수 없다고 판단하고 넘어간다. 

그렇지 않을경우 answer에 최소값을 업데이트해준다.

 

로직만 이해 잘 했으면 구현자체는 쉽기 때문에 그냥 해주면 된다.

한가지 조심해야 할 점은 첫행에 대해서 DFS를 수행할 때, 누르고 넘어간다음에 다시 원상복귀시켜줘야 한다는 것 정도?

 

 

여기서 더 최적화를 할 수 있는방법이 존재한다. 바로 비트마스킹이다.

사실 문제읽으면 바로 느낌오는데, 각 상태값이 켜져있거나 꺼져있는, 0과 1로 표현할 수 있는 상태값이기 때문이다.

한 행을 숫자하나로 표현할 수 있기 때문에 훨씬 빠르게 수행할 수 있다.

 

 
 
using namespace std;
 
 
int arr[10] = { 0 };
int temp[10] = { 0 };
int answer = 0x3f3f3f3f;
 
void switchOn(int row, int col, bool isTemp)
{
    if (isTemp == false)
    {
        arr[row] ^= 1 << col;
 
        if (row - 1 >= 0) arr[row - 1] ^= 1 << col;
        if (row + 1 < 10) arr[row + 1] ^= 1 << col;
        if (col - 1 >= 0) arr[row] ^= 1 << col - 1;
        if (col + 1 < 10) arr[row] ^= 1 << col + 1;
    }
    else
    {
        temp[row] ^= 1 << col;
 
        if (row - 1 >= 0) temp[row - 1] ^= 1 << col;
        if (row + 1 < 10) temp[row + 1] ^= 1 << col;
        if (col - 1 >= 0) temp[row] ^= 1 << col - 1;
        if (col + 1 < 10) temp[row] ^= 1 << col + 1;
    }
}
 
void allSwitchOn(int count)
{
    memcpy(temp, arr, sizeof(temp));
 
    for (int i = 1; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if (temp[i-1] & 1 << j) // 바로 윗행께 켜져있으면
            {
                ++count;
                switchOn(i, j, true);
            }
        }
    }
 
    if (temp[9] != 0) return;
 
    answer = min(answer, count);
}
 
 
void DFS(int columnIndex, int count)
{
    if (columnIndex == 10)
    {
        allSwitchOn(count);
        return;
    }
 
    DFS(columnIndex + 1, count); // 안누르고 넘어가거나
    switchOn(0, columnIndex, false); // 누르고,
    DFS(columnIndex + 1, count + 1); // 넘어간다.
    switchOn(0, columnIndex, false); // 다시 되돌려줘야 한다.
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            char input;
            cin >> input;
 
            if (input == 'O')
            {
                arr[i] |= 1 << j;
            }
        }
    }
 
    DFS(0, 0);
 
    if (answer == 0x3f3f3f3f)
    {
        cout << -1;
    }
    else cout << answer;
}
 

 

물론 인풋값이 10*10밖에 안되서 비트마스킹을 적용 하나 안하나 0ms대긴 하지만, 만약 인풋값이 엄청 크다면? 꽤나 유의미한 차이가 있을것이다.