[python] 백준 12904 A와 B

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

12904번: A와 B

 

문제 해결

• bfs를 이용해 S에서 두 경우의 수를 이어 붙인 문자열을 다시 que에 넣어가며 T가 나올 수 있는지 찾을려고 했다.
• 하지만 나타날 수 있는 문자열의 경우의 수가 너무 많아 메모리 초과가 떴다.
• 역으로 생각하여 T에서 S로 만드는 과정을 생각했다.
• 경우의 수도 역으로 생각해 뒤에 'A'이면 'A'를 떼고 que에 넣고 'B'면 'B'를 떼고 문자열을 뒤집어서 que에 넣었다.
• 빠르게 문제가 풀렸다.

 

CODE

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

S = list(input().rstrip())
T = list(input().rstrip())
l = len(S)
que = deque()
que.append(T)

while que:
    x = que.popleft()
    if x == S:
        print(1)
        exit()
    if len(x) <=l: continue
    elif x[-1] == 'A':
        x.pop()
        que.append(x)
    elif x[-1] == 'B':
        x.pop()
        x.reverse()
        que.append(x)
print(0)