책너두 - 알고리즘 챌린지[19/20]

오늘의 문제 : 불 끄기

오늘의 문제는 비트마스킹을 활용해서 풀어야했다.

비트마스킹은 고려했지만, 위에 전구가 켜져 있을 때 아래 전구를 누르는 방식에 대해 생각하지 못 해 풀지 못 했다.

풀이는 요약하자면,

1. 첫 열부터 순회하며, 현재 위치 위 전구가 켜져 있다면 press
2. 마지막 줄까지 순회 후, 맨 마지막 줄에 전구 켜진게 없다면 성공
3. 최소값 출력

import sys
from collections import deque

lights = [list(sys.stdin.readline().strip()) for _ in range(10)]
maps = [[0 for _ in range(10)] for _ in range(10)]


def press(m, y, x) :
    dx = [0, 1, 0, -1, 0]
    dy = [0, 0, 1, 0, -1]

    for i in range(5) :
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < 10 and 0 <= ny < 10 :
            m[ny][nx] = (m[ny][nx] + 1) % 2

for i in range(10) :
    for j in range(10) :
        if lights[i][j] == "O" :
            maps[i][j] = 1

cases = [101] * (1 << 10)

for case in range(1 << 10) :
    map = [maps[i][:] for i in range(10)]
    cnt = 0

    mask = 1
    for j in range(9, -1, -1) :
        if case & mask :
            press(map, 0, j)
            cnt += 1
        mask <<= 1

    for i in range(1, 10) :
        for j in range(10) :
            if map[i - 1][j] :
                press(map, i, j)
                cnt += 1

    if sum(map[9]) == 0 :
        cases[case] = cnt

print(min(cases))