[백준] 불 끄기

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

14939번: 불 끄기

일종의 brute forcing하는 문제인데 규칙성을 찾아 횟수를 줄여야 하는 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 

#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#

다음과 같이 10 x 10의 array에서

O는 불이 켜져있음을 의미하고, #는 불이 꺼져있는 것을 의미할 때, 모든 불을 끄기 위한 스위치를 누르는 최소 횟수를 return해야 합니다. (스위치를 누르면 스위치의 위, 아래, 왼쪽 오른쪽의 전구의 상태도 반대로 바뀝니다.)

 

<Solution>

만약 이 100개의 전구에 대해 모두 켤지 말지를 결정하게 된다면 총 2^100가지의 경우의 수가 나오므로 무조건 time out이 될 것을 예측할 수 있습니다. 이 search해야하는 숫자를 어떻게 줄일 수 있을지 생각해봅시다. 

 

i 번째 줄의 전구를 켜거나 끈다고 생각해봅시다. 그러면 i-1번째 줄의 전구에도 자연스럽게 변화가 생깁니다. 따라서 이 둘의 dependency를 이용해 보려 합니다.

 

전체 아이디어는 다음과 같습니다.

1. 첫번째 줄에 대해 2^10가지의 경우의 수를 시도합니다. 2. 각각의 경우의 수에 대해 2번째 줄부터 10번째 줄까지는 i 번째 줄의 전구를 변화 시킬지를 결정할 때, i-1번째 줄(row)의 전구가 켜져 있는 경우에만 바로 아래의 전구 (i번째 줄(row)의 같은 index)의 상태를 변화시킵니다.  3. 이 때, 10번째 줄이 최종적으로 모든 전구가 꺼져있는 상태이면 후보에 넣습니다. 4. 후보들 중 최솟값을 구합니다.

이렇게 하면 총 2^100의 search 횟수를 2^10으로 줄일 수 있습니다. 

 

이 때, 궁금한 점이 생길 수 있는데, 이 알고리즘이 최솟값을 보장하는가? 라는 질문을 할 수 있습니다. 

잠깐 생각을 해보면,

위와 같이 생각할 수 있습니다. 따라서 이 알고리즘은 첫째줄의 변화가 일어난 상태에 대해서 항상 최솟값을 보장합니다. 

 

실제 구현은 아래와 같습니다.

import sys
import itertools
import copy
graph_ = [list(sys.stdin.readline().rstrip()) for _ in range(10)]

move_r = [0, -1, 0, 1] # right up left down
move_c = [1, 0, -1, 0]
counter = 0
ans = int(2e9)

def oob(r, c):
    return r<0 or c<0 or r>9 or c>9

def press_swith(graph, r,c):
    global counter
    counter+=1

    graph[r][c] = 'O' if graph[r][c] == '#' else '#'
    for i in range(4):
        new_r = r+move_r[i]
        new_c = c+move_c[i]

        if not oob(new_r,new_c):
            graph[new_r][new_c] = 'O' if graph[new_r][new_c] == '#' else '#'

for e in itertools.product([0,1], repeat=10):
    counter = 0
    graph = copy.deepcopy(graph_)
    # first line
    for index, e_ in enumerate(e):
        if e_ == 0:
            continue
        else: 
            press_swith(graph, 0, index)

    for i in range(1,10):
        for j in range(10):
            if graph[i-1][j] == 'O':
                # press switch
                press_swith(graph, i,j)
    if __debug__:
        pass
    else:
        print(graph)
    if graph[9] == ['#'] * 10:
        ans = min(ans, counter)

if ans != int(2e9):
    print(ans)
else:
    print(-1)