[python] 백준 14939 불 끄기

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

14939번: 불 끄기

 

 

문제 해결

• 문제의 이해는 쉽지만 풀기 많이 어려웠던 문제
• 어디서부터 시작해야할지 많이 어렵다.
• 이 때 불 키고/끄고를 비트마스크를 이용해서 풀 수 있다고 하는데 어려워서 여러 코드를 확인하였다.
• 가장 중요한 것은 '첫 번째' 행의 불이 켜져있든 꺼져있든 스위치를 누루는 경우의 수를 모두 탐색하는 것이다.
• 이유는 첫 번째 행이 꺼져있어서 눌러 불을 켜도 다음 밑에 있는 스위치를 눌러서 다시 끌 수 있기 때문이다.
• 반대로 첫 번째 행의 스위치가 꺼진 상태로 다음 밑에 있는 스위치를 켜서 첫 번째 행의 스위치가 켜진다면 다음에 손 쓸 방법이 없게 되므로 두 번째 행의 스위치부터는 이전 스위치가 커져있는지, 꺼져있는지 확인해가며 스위치를 누룰지 말지 결정하면 된다.
• 마지막 행의 스위치를 끄고 키고까지 하고 난 다음 마지막 행의 스위치가 모두 꺼져있으면 가능하다는 신호이다.

 

CODE

import sys
input = sys.stdin.readline
from copy import deepcopy


def solve():
    dxs = [-1,1,0,0,0]
    dys = [0,0,0,-1,1]
    ans = 101
    for n in range(1<<10): # 첫 번째 행의 스위치를 어떤 것들을 누를지 설계. 꺼져있어도 누를 경우 있다는 뜻
        A = deepcopy(board) # 임시 리스트 A
        cnt = 0
        for i in range(10): # 몇 번째 열인지 선택
            if n & (1<<i): # 첫째줄
                cnt += 1
                for dx, dy in zip(dxs, dys):
                    nx = 0 + dx; ny = i + dy
                    if 0 <= nx <= 9 and 0<= ny <=9:
                        A[nx][ny] = 1 - A[nx][ny]

        for i in range(1, 10):
            for j in range(10):
                if not A[i-1][j]:continue
                for dx, dy in zip(dxs, dys):
                    nx = i + dx; ny = j + dy
                    if 0 <= nx <= 9 and 0<= ny <= 9:
                        A[nx][ny] = 1 - A[nx][ny]
                cnt += 1
        if all(i==0 for i in A[-1]): # 마지막 행이 모두 꺼져있으면
            ans = min(cnt, ans)
    return ans
if __name__ == "__main__":
    board = []
    for _ in range(10):
        tmp = list(input().strip())
        for j in range(10):
            if tmp[j] == 'O':
                tmp[j] = 1
                continue
            tmp[j] = 0
        board.append(tmp)
    answer = solve()
    print(answer if answer < 101 else -1)