14939 : 불 끄기 Python

14939번: 불 끄기

어제 99클럽 알고리즘 스터디에서 봤던 문제랑 유사하지만 약간 다른 점이 있다.

• 불가능한 경우가 존재하고 불가능할 경우 -1을 출력해야한다는 점
• 상태가 켜고 끄는 2가지 경우에 열이 10칸이므로 한 줄당 2^10(1024)가지의 경우의 수가 있다는 점
  • 어제는 4방향 * 최대 8칸으로 4^8(65,536)가지의 경우의 수

어제 첫 줄부터 고정시켜 놓으며 바로 아래 줄의 회전 횟수가 정해진다는 아이디어를 듣고 나서 문제를 풀어보려고 시도했으나 이를 어떻게 구현해야할지 감이 잘 안잡혔다. 결국 다른 분들 풀이를 참조했다.

[백준] 14989 - 불 끄기 💡 / 플래티넘 5 / 브루트포스 & 그리디

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

풀이

현재 줄의 상태에 따라 바로 아랫줄의 점등 여부 정해진다고 했다.

따라서 첫 줄의 스위치를 조작하면 그 뒤로는 스위치를 누를지 말지 선택하지 않고 윗줄에 스위치에 종속된다.

만약 위와 같이 보드가 있을 때는 윗 칸이 켜져 있는 (1,0), (1,2), (1,4) 의 스위치를 눌러야 한다. 첫 번째 줄의 점등 여부로 두 번째칸 불의 점등여부가 결정됐다.

이와 같이 세 번째 줄의 스위치 조작 여부는 이전 줄인 두 번째 줄의 불이 켜져있는지 확인하면 된다.

 

이렇게 위에서 아래로 탐색하면서 마지막 줄까지 내려왔을 경우에는 마지막 줄만 불이 다 꺼져있는지 확인하면 된다. 왜? 우리는 바로 윗줄의 불이 켜져 있을 때만 아랫줄의 불을 껐다. 이는 곧 현재 줄의 위는 모두 불이 꺼진 상태임을 의미한다. 따라서, 우리는 마지막 줄만 모두 꺼져 있는지 확인하면 모든 칸이 꺼져 있는지 알 수 있다.

 

그럼 첫 줄은 어떻게 켜고 끄느냐?

첫 줄의 전등에서 나올 수 있는 모든 경우의 수를 다 해보면 된다. 전등의 상태가 켜기, 끄기 두 개 밖에 없고 10개의 전등이 있으므로 2^10, 1024가지로 충분히 작다. 또한, 이렇게 2가지 상태에 적은 대상은 비트마스킹을 사용하기 최적의 조건이다.

따라서 첫 줄의 모든 경우의 수를 다 확인하는 것은 아래와 같이 나타낼 수 있다.

for tries in range(1 << 10):
        board = deepcopy(_map) # 원본을 변화시키지 않고 깊은 복사
        cnt = 0

        for col in range(10):
                if tries & (1 << col): # 선택된 조합을 확인
                        change_status(0, col, board) # 불 상태 변화
                        cnt += 1

처음 코드를 볼 때는 tries가 무엇을 하는지 잘 몰랐다. 여기서 tries가 하는 일은 “나는 첫 줄의 상태는 잘 모르겠고 선택된 열들의 전등 상태를 변화시켜 볼게”이다. 이렇게 전등 상태를 변화시키면 횟수를 + 1 해줬다. 이는 나중에 모든 불이 다 꺼졌으면 이 횟수로 갱신시키기 위함이다.

 

그리고 우리는 모든 경우의 수를 확인하기 때문에 원본이 변화하면 그 심각한 문제가 발생한다. 따라서, deepcopy 메서드를 통해 깊은 복사해줬고 이를 변화시키면서 탐색했다.

 

자 이제 두 번째 줄 부터는 바로 윗 칸의 상태에 따라 켜고 끌지 정하면 된다. 코드는 다음과 같다.

for row in range(1, 10):  # 1줄부터 9번째 줄까지
    for col in range(10):  # 모든 열에 대해
        if board[row - 1][col] == STATUS[ON]:  # 바로 윗 칸이 불이 켜진 상태라면
            change_status(row, col, board)
            cnt += 1

마지막에 모든 불이 꺼졌는지 확인하고 꺼졌다면 이 횟수와 기존의 저장된 값을 비교해서 더 작은 값으로 갱신하면 된다. 만약 모든 경우의 수를 확인했는데도 불가능하면 초기에 저장해놨던 INF 값이 남아있을 것이다. 이 때는 -1을 출력하면 된다.

전체 코드

import sys
from copy import deepcopy

# print = sys.stdout.write
input = sys.stdin.readline

# 반드시 아래 두 라인 주석처리 후 업로드
# f = open("input.txt", "rt")
# input = f.readline
# 위 두라인 주석처리 후 업로드
INF = float("inf")
SIZE = 10
STATUS = ("O", "#")
ON, OFF = 0, 1

_map = [list(input().rstrip()) for _ in range(SIZE)]

dy, dx = (-1, 1, 0, 0, 0), (0, 0, 0, -1, 1)  # 상, 하, 현재 칸, 좌, 우


def change_status(y, x, board):
    for i in range(5):
        ny, nx = dy[i] + y, dx[i] + x
        # 범위를 벗어나면 넘어감
        if ny >= SIZE or nx >= SIZE or ny < 0 or nx < 0:
            continue

        idx = OFF if board[ny][nx] == STATUS[ON] else ON
        board[ny][nx] = STATUS[idx]


def is_aligned(board):
    if board[-1].count(STATUS[OFF]) != SIZE:
        return False
    return True


def main():
    ans = INF
    for tries in range(1 << 10):
        board = deepcopy(_map)
        cnt = 0

        for col in range(10):
            if tries & (1 << col):  # 선택된 조합의 스위치들을 눌러봄
                cnt += 1
                change_status(0, col, board)  # 스위치 끄기

        for row in range(1, 10):  # 1줄부터 9번째 줄까지
            for col in range(10):  # 모든 열에 대해
                if board[row - 1][col] == STATUS[ON]:  # 바로 윗 칸이 불이 켜진 상태라면
                    change_status(row, col, board)
                    cnt += 1

        # 마지막 줄을 확인했을 때 모든 불이 꺼져 있다면
        if is_aligned(board):
            ans = min(ans, cnt)

    print(ans if ans != INF else -1)


if __name__ == "__main__":
    main()