[Python] 백준 <12904-A와 B>

https://www.acmicpc.net/problem/12904

 

- 시간 초과 (BFS 정순)

import sys
from collections import deque
input = sys.stdin.readline

def checkStr(xx):
    dq = deque()
    dq.append(xx)

    check = 0
    while dq:
        now = dq.popleft()
        # 단어가 같으면 1 리턴
        if now == T:
            return 1
        # 길이가 더 길어지면 now 건너뛰기
        elif len(now) > max_in:
            continue
        
        # 두가지 경우 모두 해서 dq에 집어넣기
        oneS = now+'A'
        twoS = ''
        for i in now:
            twoS = i+twoS
        twoS = twoS+'B'

        dq.append(oneS)
        dq.append(twoS)
    return 0

S = input().strip()
T = input().strip()
max_in = len(T)
dap = checkStr(S)

print(dap)

 

- 정답 코드 (BFS 역순)

import sys
from collections import deque
input = sys.stdin.readline

def checkStr(T):
    dq = deque()
    dq.append(T)

    check = 0
    while dq:
        now = dq.popleft()
        if now == S:
            return 1
        elif len(now) < len(S):
            continue
    
        # 뒤가 A면 A 제거
        if now[-1] == 'A':
            dq.append(now[:-1])
        
        # 뒤가 B면 B 제거 후 뒤집기
        if now[-1] == 'B':
            ss = ''
            for i in now[:-1]:
                ss = i+ss
            dq.append(ss)
    return 0

S = input().strip()
T = input().strip()
dap = checkStr(T)

print(dap)