백준 14939 불 끄기

비트마스킹 분류로 되어있는 문제이다.

처음 접근할때, 모든 스위치 상황을 비트마스킹으로 만들까 했는데, 10*10 맵을 비트마스킹으로 표시하면 이걸 담을 자료형이 마땅치 않아 접었다. 물론 여러개의 변수를 사용해서 만들 수는 있지만, 그렇게까지 해야할까... 싶었다.

문제가 속한 다른 분류에 그리디가 있어서 한번 생각을 꼬아봤다. 맨 윗줄만 탐색하고 나머지는 그때 그때 상황에따라 계산해보자...

 

첫 줄에 불을 켜냐 끄냐 경우의 수는 2^10이다. 따라서 그 경우의 수 만큼 탐색을 한다. 첫 줄의 상황에 맞게 스위치를 눌러놓고, 다음 줄 부터 마지막 줄 까지는 윗 줄 같은 열이 켜져있을 때 스위치를 누르는 선택을 한다. 이 때, toggle() 함수를 따로 만들어, temp[][]배열에 변경사항을 실행해준다.

 

이렇게 전부 순회하면서 스위치를 켜고 끈 다음, 마지막 줄이 전부 꺼져있는지 확인해 해당 조건이 가능한지 확인한다. 확인이 된 경우 스위치 횟수를 비교하며 최소값을 찾아 리턴하면 답이다!\

#include <iostream>
#include <climits>

int dy[] = {0, 0, 1, 0, -1};
int dx[] = {0, 1, 0, -1, 0};
char map[11][11];
char temp[11][11];

void sw_toggle(int n, int m)
{
    for (int i = 0; i < 5; i++)
    {
        int ny = n + dy[i];
        int nx = m + dx[i];

        if (ny < 0 || ny >= 10 || nx < 0 || nx >= 10)
            continue;

        if (temp[ny][nx] == '#')
            temp[ny][nx] = 'O';
        else
            temp[ny][nx] = '#';
    }
}

int main()
{
    std::cin.tie(0);

    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
            std::cin >> map[i][j];
    }

    int answer = INT_MAX;

    for (int sw = 0; sw < (1 << 10); sw++) // 첫줄 스위치 경우의 수들
    {
        int cnt = 0;

        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
                temp[i][j] = map[i][j];
        }

        for (int i = 0; i < 10; i++)
        {
            if (sw & (1 << i))
            {
                cnt++;
                sw_toggle(0, i); // 첫줄 스위치 순회하며 누르는 경우일때 누르기.
            }
        }

        for (int i = 1; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                if (temp[i - 1][j] == 'O') // 윗줄 같은열이 켜져있을때
                {
                    cnt++; 
                    sw_toggle(i, j); // 끄기!
                }
            }
        }
        
        bool notAv = false;
        for (int i = 0; i < 10; i++)
        {
            if (temp[9][i] == 'O') // 마지막 줄 켜져있으면 
            {
                notAv = true; // 정답상황 아님
                break;
            }
        }

        if (!notAv)
            answer = std::min(cnt, answer);
    }
    if (answer != INT_MAX)
        std::cout << answer;
    else
        std::cout << -1;
}

 

모든 경우의 수를 비트마스킹으로 처리하려는 초기 접근이 좀 무리였던것 같다. 상황들에서 일부를 떼내어 파생 가능한지 고민을 해 보아야 겠다. 

 

오늘도 평온한 하루가 되길. 슨민.

 

ref : 글 읽기 - 두 코드의 차이점을 잘 모르겠습니다.. (acmicpc.net)