[백준] 14939. 불 끄기 - 파이썬

[Platinum V]

 

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

14939번: 불 끄기

 

백조의 호수 이후로 오랜만에 풀어보는 플래티넘 문제. ^ㅁ^

 

풀이

우선, 10x10 배열 - 100칸이기에, 너무 무모한 Brute-Forcing만 아니면, TLE는 나오지 않겠거니 하고 생각했다.

처음 보자마자 떠올린 것은, 한 번 누른 칸은 다시 누를 일이 없지 않을까? 라는 것.

한 번 눌린 칸을 다시 누르게 되면, 5칸이 결국 누르기 전의 상태와 같아지는 것이므로, 100칸에 대해서 각각 누를 지 말 지만 결정하면 된다는 것!

---

... 여기까지는 생각해냈는데, 이후 30분가량 진척이 없었다.

실마리를 찾으려 다른 풀이 (https://technicolour.tistory.com/19) 를 살짝 봤더니,

첫째 줄부터 누를 지 말 지 결정하면서 내려가나, 첫째 줄의 모든 경우의 수(2^10 = 1024)에 대해서만 생각해주면 되었다는 것.

왜냐하면 결국 첫째 줄을 모두 처리한 후, 첫째 줄에 켜진 전구가 남아있다면, 무조건 두번째 줄의 바로 아래 전구를 눌러 꺼줘야 하기 때문에, 첫째 줄의 경우의 수만 생각하면, 2~10줄에서 처리해줘야 할 경우의 수는 1가지밖에 남지 않는다. (3번째 줄에서는 1번째 줄의 켜진 전구를 꺼줄 수 없기 때문.)

 

참 어렵긴 하다. 이걸 어떻게 생각해낼 수 있을까?

마치 수능 수학 30번 풀이의 번뜩이는 아이디어를 떠올려야 하는 그 느낌..

 

input은 0, 1을 저장하는 2차원 배열로 처리하였고,

copy by reference를 막기 위해 copy.deepcopy() 사용,

토글은 함수로 처리,

모든 전구가 꺼져 있는 지 확인은 max함수로 처리함 (근데 이건 마지막 줄만 확인해도 된다.)

 

AC.

import copy
from itertools import product
bulb = [list(input()) for _ in range(10)]

for i in range(10):
    for j in range(10):
        if bulb[i][j] == "#":
            bulb[i][j] = 0
        else:
            bulb[i][j] = 1


def toggle(B, i, j):
    B[i][j] = (B[i][j] + 1) % 2
    if i+1 < 10:
        B[i+1][j] = (B[i+1][j] + 1) % 2
    if i-1 >= 0:
        B[i-1][j] = (B[i-1][j] + 1) % 2
    if j+1 < 10:
        B[i][j+1] = (B[i][j+1] + 1) % 2
    if j-1 >= 0:
        B[i][j-1] = (B[i][j-1] + 1) % 2


results = []

# 첫 줄의 경우의 수 2^10 가지
isToggles = list(product([0, 1], repeat=10))

for isToggle in isToggles:
    result = 0
    b = copy.deepcopy(bulb)

    # 첫 줄 세팅
    for i, k in enumerate(isToggle):
        if k == 1:
            toggle(b, 0, i)
            result += 1

    # 2~10째줄
    for i in range(1, 10):
        for j in range(0, 10):
            # 바로 위 전구가 켜져 있다면 toggle.
            if b[i-1][j] == 1:
                toggle(b, i, j)
                result += 1

    # 모든 전구가 꺼져 있다면 성공.
    if max(map(max, b)) == 0:
        results.append(result)

if len(results) == 0:
    print(-1)
else:
    print(min(results))