[백준] 14939 - 불 끄기

1. 문제

14939번: 불 끄기

2. 개요

10 x 10 모양으로 된 전구 100개 모음이 있다.

전구에 달린 스위치를 누르면 본인을 포함해 상하좌우의 전구의 상태가 바뀐다.

전구 100개의 상태가 주어질 때 모든 전구를 끄기 위해 스위치를 누르는 최소 횟수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

https://app155.github.io/algorithm/bj_2138/

2138 - 전구와 스위치 문제와 개념은 똑같은데 2차원이 됐을 뿐이다.

위쪽부터 차례대로 전구의 스위치를 작동한다면,

바로 위의 전구의 상태에 간섭 가능한 스위치는 그 바로 아래 전구의 스위치가 된다.

즉, 최상단의 스위치의 동작 여부만 판단한다면 그 아래 행부터는 하나씩 훑으며 판단이 가능해진다.

최상단에는 전구 10개가 있고 각각은 키거나 끄는 두 가지 상태가 있다.

따라서 2^10 인 1024까지 탐색하며 이를 이진수로 만들어 동작시킨다.

첫 행의 전구의 동작이 완료되었다면, 다음 행부터 전구를 하나씩 돌며 바로 위의 전구가 켜져있다면 스위치를 꺼준다.

모든 전구를 탐색하고 켜진 전구가 없다면 답을 갱신하고 다시 첫 행 전구 탐색으로 되돌아간다.

1024번 반복을 완료했는데 답이 초기값 그대로라면 불가능한 경우이므로 -1을, 아니라면 답을 출력한다.

3-2. Python

import sys
import copy

def pushswitch(y, x):
    dirY, dirX = [-1, 0, 1, 0, 0], [0, -1, 0, 1, 0]

    for i in range(5):
        nextY, nextX = y + dirY[i], x + dirX[i]

        if 0 <= nextY < 10 and 0 <= nextX < 10:
            _board[nextY][nextX] = (_board[nextY][nextX] + 1) % 2

board = []

for i in range(10):
    r = list(sys.stdin.readline().rstrip())

    for j in range(10):
        if r[j] == '#':
            r[j] = 0
        else:
            r[j] = 1

    board.append(r)

answer = 555555555
for i in range(1024):
    tmpanswer = 0
    tmp = bin(i)[2:]
    if len(tmp) < 10:
        tmp = '0' * (10 - len(tmp)) + tmp

    _board = copy.deepcopy(board)
    for j in range(10):
        if tmp[j] == '1':
            pushswitch(0, j)
            tmpanswer += 1

    for k in range(1, 10):
        for l in range(10):
            if _board[k-1][l] == 1:
                pushswitch(k, l)
                tmpanswer += 1

    total = 0
    for row in _board:
        total += sum(row)

    if total == 0:
        answer = min(answer, tmpanswer)

print(answer) if answer != 555555555 else print(-1)

3-3. C#

internal class Program
{
    static int[,] board;
    static int[,] tmpboard;
    static void Main(string[] args)
    {
        board = new int[10, 10];
        for (int i = 0; i < 10; i++)
        {
            string input = Console.ReadLine();

            for (int j = 0; j < 10; j++)
            {
                if (input[j] == '#')
                    board[i, j] = 0;
                else
                    board[i, j] = 1;
            }
        }
        int answer = 55555555;

        for (int i = 0; i < 1024; i++)
        {
            tmpboard = board.Clone() as int[,];
            int tmpanswer = 0;
            string binum = Convert.ToString(i, 2);
            binum = string.Format("{0:D10}", long.Parse(binum));

            for (int j = 0; j < 10; j++)
            {
                if (binum[j] == '1')
                {
                    PushSwitch(0, j);
                    tmpanswer++;
                }
            }

            for (int k = 1; k < 10; k++)
            {
                for (int l = 0; l < 10; l++)
                {
                    if (tmpboard[k - 1, l] == 1)
                    {
                        PushSwitch(k, l);
                        tmpanswer++;
                    }
                }
            }

            int total = 0;
            for (int a = 0; a < 10; a++)
            {
                for (int b = 0; b < 10; b++)
                {
                    total += tmpboard[a, b];
                }
                if (total > 0)
                    break;
            }

            if (total == 0)
            {
                answer = Math.Min(answer, tmpanswer);
            }
        }

        answer = answer == 55555555 ? -1 : answer;
        Console.WriteLine(answer);

    }

    static void PushSwitch(int y, int x)
    {
        int[] dirY = { -1, 0, 1, 0, 0 };
        int[] dirX = { 0, -1, 0, 1, 0 };

        for (int i = 0; i < 5; i++)
        {
            int nextY = y + dirY[i];
            int nextX = x + dirX[i];

            if (nextY < 0 || nextY >= 10 || nextX < 0 || nextX >= 10)
                continue;

            tmpboard[nextY, nextX] = (tmpboard[nextY, nextX] + 1) % 2;

        }
    }
}