[백준][14939][Python 파이썬][P4] 불 끄기

문제

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라

입력

10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.

출력

모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.

 

 

테스트케이스

#O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O#	O########O #OOOOOOOO# #OOOOOOOO# #OOOOOOOO# #OOOOOOOO# #OOOOOOOO# #OOOOOOOO# #OOOOOOOO# #OOOOOOOO# O########O	#O#O#O#O#O O#O#O#O#O# #O#O#O#O#O O#O#O#O#O# #O#O#O#O#O O#O#O#O#O# #O#O#O#O#O O#O#O#O#O# #O#O#O#O#O O#O#O#O#O#	OOOOOOOOOO O#O#OO##OO O###OO##OO O#O#O#OO#O OOOOOOOOOO O##OOO##OO O#O#OO#O#O O##OOO#O#O O#O#OO##OO OOOOOOOOOO
4	100	38	47

 

-1나오는 TC 찾아보려고 했는데 잘 안보이네요..

코드

import sys

input = sys.stdin.readline

board = ''

for i in range(10):

    cmd = list(input().rstrip())

    for j in range(10):

        if cmd[j] == "#":

            board += "0"

        else:

            board += "1"

board = int(board, 2)

answered = False

ans = 1000

def press(curboard, button):

    tempset = set()

    tempset.add(button)

    if button // 10 != 0:

        tempset.add(button-10)

    if button // 10 != 9:

        tempset.add(button+10)

    if button % 10 != 0:

        tempset.add(button-1)

    if button % 10 != 9:

        tempset.add(button+1)

    for x in tempset:

        curboard ^= (1 << x)

    return curboard

for i in range(1 << 10):

    cnt = 0

    tempboard = board

    for j in range(10):

        if i & (1 << j):

            tempboard = press(tempboard, j)

            cnt += 1

    for j in range(1, 10):

        for k in range(10):

            locate = 10*j + k

            if tempboard & (1 << (locate-10)):  # 한줄 아래가 켜져있으면

                tempboard = press(tempboard, locate)

                cnt += 1

    if tempboard == 0:

        ans = min(ans, cnt)

if ans == 1000:

    print(-1)

else:

    print(ans)

 

후기

와 어려웠다....

솔직히 처음 보자마자 막막하긴 했는데

일단은 눌렀을때 3개 이상 꺼지면 켜져있는부분이 점점 줄어들테니까

그런점들을 골라서 BFS하는 코드로 짰다

 

import sys

from collections import deque

input = sys.stdin.readline

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

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

board = ''

visited = set()

for i in range(10):

    cmd = list(input().rstrip())

    for j in range(10):

        if cmd[j] == "#":

            board += "0"

        else:

            board += "1"

board = int(board, 2)

visited.add(board)

Q = deque()

Q.append((0, board))

answered = False

while Q:

    level, curboard = Q.popleft()

    if curboard == 0:

        print(level)

        answered = True

        break

    for i in range(100):

        cnt = 0

        tempset = set()

        tempset.add(i)

        if curboard & (1 << i):

            cnt += 1

        if i // 10 != 0:

            tempset.add(i-10)

            if curboard & (1 << (i-10)):

                cnt += 1

        if i // 10 != 9:

            tempset.add(i+10)

            if curboard & (1 << (i+10)):

                cnt += 1

        if i % 10 != 0:

            tempset.add(i-1)

            if curboard & (1 << (i-1)):

                cnt += 1

        if i % 10 != 9:

            tempset.add(i+1)

            if curboard & (1 << (i+1)):

                cnt += 1

        if cnt < 3:

            continue

        tempnum = 0

        for x in tempset:

            tempnum ^= (1 << x)

        tempboard = curboard ^ tempnum

        if tempboard in visited:

            continue

        Q.append((level+1, tempboard))

        visited.add(tempboard)

if not answered:

    print(-1)

 

이런 느낌으로.

이것도 솔직히 비트마스킹 상상해서 푸느라 꽤 힘들었고..

근데 TC는 되는데 시간초과가 되어서 하.. 많이누르면 답없긴 하겠다.. 생각하고 막막하던 와중

실제로 풀면 어떻게 풀지? 생각하다가

어차피 한쪽 줄만 어케든 하면

나머지는 그 줄에있는걸 없애는 방향으로 진행하면 되니까?

-> 첫줄만 완전탐색하면 되겠다 -> 2^10이면 할만하다 라는 생각을 하고 구현했다

 

예전에 모바일 게임 Exponential Idle에서

https://exponential-idle-guides.netlify.app/guides/asd/

Minigames - Exponential Idle Guides

이와 같은 하나를 바꾸면 옆이 모두 돌아가는 Arrow Puzzle을 풀면서 공식 공부하고 했었는데

이걸 조금 쉽게 바꾼 문제지 않았나 싶다

 

하지만 Arrow Puzzle은 줄 개수가 줄어드는 부분에서 이 문제와 같이 전 칸을 확인하고 마음대로 쓰는게 불가능해서

만약 저런경우에는 어떻게 풀어야 할까...

세로로 푼다고 치면 왼쪽에서 완전탐색하고 / 중앙까지 맞추고 / 오른쪽에서 출발해서 가는 방법으로? 될라나?