b_전구와 스위치_2138

문제

i변경시 , i-1, i, i+1 전구상태바뀜
? ^ 1 = 반대

일치하는지여부
둘이 ^하면 다른부분만1되서나옴

주요로직일치하지않는부분을바꾼다

정답

• 2번 누르면 안 누른 것과 같다
  • 한번 누르거나 안 누르거나
• 순서는 상관없음
• 하나를 누르냐 마냐의 포인트만잡으면 나머지것들이 결정됨
  • 왜냐 그 하냐를 누르냐마냐의 경우의 수밖에 없기때문이지

import sys

input = sys.stdin.readline

# <span id="스위치를-눌렀을-때-상태-변경을-해주는-함수"></span>스위치를 눌렀을 때 상태 변경을 해주는 함수
def reverse(bulbs, count):
    for i in range(1, N-1):
        if bulbs[i-1] != target[i-1]:
            count += 1
            for j in range(i-1, i+2):
                bulbs[j] = not bulbs[j]
    # 마지막 전구만 따로 처리
    if bulbs[N-1] != target[N-1]:
        count += 1
        bulbs[N-2] = not bulbs[N-2]
        bulbs[N-1] = not bulbs[N-1]
    if bulbs == target:
        return count
    else:
        return -1


N = int(input())

# <span id="not을-이용해-간편하게-처리하고-싶어서-0false-1true의-bool-값으로-바꾸었다"></span>not을 이용해 간편하게 처리하고 싶어서 0:False, 1:True의 bool 값으로 바꾸었다.
off = list(map(bool, map(int, input().rstrip())))

# <span id="0번째-스위치를-누른-상태를-저장하는-리스트"></span>0번째 스위치를 누른 상태를 저장하는 리스트
on = off.copy()
on[0] = not on[0]
on[1] = not on[1]

target = list(map(bool, map(int, input().rstrip())))

# <span id="처음부터-상태가-같은-경우-스위치를-눌러줄-필요가-없으니-0-출력"></span>처음부터 상태가 같은 경우 스위치를 눌러줄 필요가 없으니 0 출력
if off == target:
    print(0)
else:
    # 0번째 전구를 안눌렀을 때
    count = reverse(off, 0)
    if count != -1:
        print(count)
    else:
        # 0번째 전구를 눌렀을 때
        count = reverse(on, 1)
        print(count if count else -1)

나의 오답

import sys
from collections import deque
N = int(sys.stdin.readline().strip())
mask = (1 << N) -1
# <span id="printbinmask"></span>print(bin(mask))
before= int(sys.stdin.readline().strip(),2)
after= int(sys.stdin.readline().strip(),2)

done = set([before])

def solution():
    global N,mask,before,after,done
    que = deque([(before,0)])
    while que:
        # print(que,done)
        nque = deque()
        for tmp,cnt in que:
            if after == tmp:
                return cnt
            dif = tmp ^ after
            dif_str = bin(dif)
            # print(dif_str)
            limit = len(dif_str)-2
            for i in range(limit):
                s = dif_str[limit+1-i]
                if s != '1':
                    continue
                convert = 0b111 << (i - 1) if i >0 else 0b11
                ntmp = (tmp ^ convert) & mask
                # print("바꿈",i,bin(convert),bin(ntmp))
                if ntmp in done:
                    continue
                if after == ntmp:
                    return cnt+1
                nque.append((ntmp,cnt+1))
                done.add(ntmp)
        que = nque
    return -1
        
print(solution())