[python] 백준 14939 : 불 끄기

문제 링크
https://www.acmicpc.net/problem/14939

접근

전구가 줄마다 on/off 되어있는 문제라 비트마스킹을 생각했다.
그런데 각 줄마다 2^10 == 1024 만큼의 공간이 필요한데, 제대로 경우를 나누려면 이 공간을 10번을 더 곱해줘야하는 (2^100...) 상황이었다.

이런저런 방법을 생각해보았지만 도저히 떠오르지 않아 다른 블로그를 참고하였다...

https://lem0nad3.tistory.com/7

---

풀이

풀이는 생각보다 간단하다. (떠올리는게 불가능했지만...)

1. 첫번째 줄에서 나올 수 있는 (전구 누르는) 모든 경우의 수(1024개)에 대해서
   1-1. 현재 경우의 수에 대한 전구를 세팅해준다.
   1-2. 두번째 줄부터는 각 열마다 순회하면서, 현재 위치 한칸 위에 칸에 전구가 켜져있으면 현재 위치의 전구를 press 한다.
   1-3. 마지막 줄까지 다 확인했으면, 맨 마지막 줄에 전구 켜진게 없으면 성공! 있으면 실패!
2. 최소로 누른 값을 출력

코드로 보는 것이 더 쉬울 수도 있다.

first_line_press_case = [101] * (1 << 10)
for case in range(1 << 10):
    tmp_board = [board[i][:] for i in range(10)]  # copy board to tmp board
    cnt = 0

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

    # 2번 줄부터 끝까지
    for i in range(1, 10):
        for j in range(10):
            if tmp_board[i - 1][j]:  # 현재 위치 위에 전구가 켜져있으면
                press(tmp_board, i, j)  # 현재 위치 press
                cnt += 1

    # 만일 마지막줄 전구 다 꺼져있으면 성공!
    if sum(tmp_board[9]) == 0:
        first_line_press_case[case] = cnt

첫 줄의 전구를 누르는 경우 모두 탐색한다. 첫 줄이 기준이다.

set case 부분은 그냥 현재 case에 맞게 전구를 세팅? 눌러주는 것이다.
(현재 case는 각 비트가 전구 위치에 대응한다고 보면 됨)

2번 줄부터 10번 줄까지 내려가면서, 각 줄의 열을 확인한다.
이때 확인하는 칸의 윗칸을 살펴볼 것인데, 만약 윗 칸의 전구가 켜져있다면 현재 확인하는 칸을 press 해준다. (누른 횟수도 증가!)

핵심!!! i번 줄에 대한 작업을 마치면(i번 행 한번 다 봤으면) i-1번 줄은 전구가 모두 꺼져있는 상태가 된다

만약 10번 줄까지 다 탐색을 했다면, 마지막 줄(10번 줄)을 살펴본다.
마지막줄의 전구가 다 꺼져있다면 성공이다. 어차피 위의 작업을 통해 9번 줄까지는 전구가 다 꺼져있을 것이고, 10번줄까지 다 꺼져있다면, 모든 전구가 다 꺼져있다는 것이다.

---

이러한 발상은 아직은 떠올리기가 너무 어려운 것 같다.
이런 식의 문제가 코테에 나오면 풀 수 있을지 의문이다...
일단은 최대한 많은 유형과 알고리즘을 익하는 것이 중요한 것 같다.

정답 코드

import sys

sys.setrecursionlimit(10 ** 8)  # pypy 제출시 삭제!
input = lambda: sys.stdin.readline().rstrip()
in_range = lambda y, x: 0 <= y < 10 and 0 <= x < 10

dy = [0, 0, 1, 0, -1]
dx = [0, 1, 0, -1, 0]


def press(b, y, x):
    for i in range(5):
        ny, nx = y + dy[i], x + dx[i]
        if in_range(ny, nx):
            b[ny][nx] = (b[ny][nx] + 1) % 2


board = [[0 for _ in range(10)] for _ in range(10)]

for i in range(10):
    line = input()
    for j in range(len(line)):
        if line[j] == "O":
            board[i][j] = 1

first_line_press_case = [101] * (1 << 10)
for case in range(1 << 10):
    tmp_board = [board[i][:] for i in range(10)]  # copy board to tmp board
    cnt = 0

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

    # 2번 줄부터 끝까지
    for i in range(1, 10):
        for j in range(10):
            if tmp_board[i - 1][j]:  # 현재 위치 위에 전구가 켜져있으면
                press(tmp_board, i, j)  # 현재 위치 press
                cnt += 1

    # 만일 마지막줄 전구 다 꺼져있으면 성공!
    if sum(tmp_board[9]) == 0:
        first_line_press_case[case] = cnt


print(min(first_line_press_case))