불 끄기

• Lights Out 라는 유명한 퍼즐을 가지고 만든 문제.
• 우선 관찰할 수 있는 것은 같은 스위치를 1번 넘게 누르는 것은 최적값이 될수 없다는 것이다. 따라서 최적방법은 몇개의 스위치를 골라서 한번씩 누르는 방법이 된다. 스위치가 100개니까, 2^100가지의 스위치 조합을 다 시도해보면 되긴 한다. 각 스위치 조합은 최대 100번 스위치를 누르면 되니까 O(100 * 2^100) 이면 이렇게 풀어도 돌아갈것 같기도 하다..
• 하지만 이 퍼즐을 원래 어떻게 푸는지 알고 있다면 더 쉽게 푸는 아이디어를 떠올릴수 있다. 원래 이 퍼즐을 손으로 푸는 방법은, 첫째줄을 건드리지 않고, 둘째줄부터 스위치를 조작해나가는 것이다. 첫번째줄의 c번째 칸이 켜져있다면 그것을 끄기 위해서는 두번째줄의 c번째 칸의 스위치를 반드시 눌러야 한다. 따라서 첫번째줄을 모두 끄기 위해서 눌러야 하는 두번째줄의 스위치들은 고정되어있다. 두번째줄 스위치를 조작해서 첫번째 줄을 모두 끄고 나면, 이제 세번째줄의 스위치를 조작해서 두번째줄의 스위치를 끄게 된다. 이 작업을 마지막줄까지 반복하면 최종적으로 마지막줄을 제외한 모든 줄의 전구를 끌 수 있다. 그리고 마지막줄에 켜져있는 전구 패턴은 2^10 개의 가짓수로 압축된다. 실제 퍼즐게임은 5×5 보드에서 하므로 마지막줄의 가능한 패턴은 2^5개이고 대칭을 고려하면 2^4개로 줄어든다. 그럴면 이 16가지의 패턴에 대해서 어떤 스위치를 눌러야 하는지만 외우고 있다면 그것을 적용해서 퍼즐을 풀수 있다.
• 마찬가지 아이디어를 적용한다. 첫줄에 대해서 어떤 스위치 조합을 적용하고 나면, 둘째줄 이후로는 눌러야 될 스위치가 고정되있다는 것이다. 따라서 2^10가지의 조합에 대해서만 시도해보면 풀수 있다. 시간복잡도는 O(2^10 * 100)이 된다.
• 최소한으로 눌러야하는 스위치의 갯수를 구하라는 말 때문에, 2^10가지를 모두 다 시도해보고 성공했을 경우들에 대해서 스위치 갯수의 최솟값을 구하려고 할 수 있는데, 실제로 답이 될수 있는 것은 2^10가지중 단 한가지 뿐이다. 그래서 모든 스위치를 끌수 있는 조합을 찾았다면 그때의 스위치 갯수를 출력하고 거기서 중단해도 상관없다.

"""Solution code for "BOJ 14939. 불 끄기".

- Problem link: https://www.acmicpc.net/problem/14939
- Solution link: http://www.teferi.net/ps/problems/boj/14939

Tags: [Ad Hoc]
"""

import itertools

SIZE = 10
ON = 'O'
OFF = '#'
DELTAS = ((0, 0), (-1, 0), (1, 0), (0, -1), (0, 1))


def press(grid, r, c):
    for dr, dc in DELTAS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < SIZE and 0 <= nc < SIZE:
            grid[nr][nc] = ON if grid[nr][nc] == OFF else OFF


def main():
    init_grid = [input() for _ in range(SIZE)]

    for i in range(SIZE + 1):
        for cols in itertools.combinations(range(SIZE), i):
            grid = [list(row) for row in init_grid]
            count = i
            for c in cols:
                press(grid, 0, c)
            for r in range(1, SIZE):
                for c in range(SIZE):
                    if grid[r - 1][c] == ON:
                        press(grid, r, c)
                        count += 1
            if all(x == OFF for x in grid[-1]):
                print(count)
                return
    print('-1')


if __name__ == '__main__':
    main()