백준 12904 A와B

import sys
from collections import deque

first = sys.stdin.readline().rstrip()
first_len = len(first)

last = sys.stdin.readline().rstrip()

queue = deque()
queue.append(last)

while queue:
    temp = queue.popleft()

    if len(temp) == first_len:
        if temp == first:
            print(1)
        else:
            print(0)
        break

    if temp[-1] == 'A':
        temp = temp[:-1]
        queue.append(temp)

    elif temp[-1] == "B":
        temp = temp[:-1]
        temp = temp[::-1]
        queue.append(temp)

A 와 B는 나름의 규칙으로 결과를 찾을수 있나 없나에 대한 문제이다.

규칙은 두개가있다.

뒤에 A를 붙인다.

현재 문자열 뒤집고 B를 붙인다.

​

그래서 B 가 시작이고 ABBA 를 만들수 있나 없나를 따지는 문제인데.

나는 처음에는 각 조건들에 해당하는 문자열을 BFS로 돌릴려했다.

근데 이렇게 하면 되긴하는데 메모리초과 or 시간초과가 뜬다.

그래서 차라리 ABBA 에서 B를 맞추면 될꺼라 생각했다.

​

현재 맨 뒷자리 = A

ABB 에서 A 만 붙임

​

현재 맨 뒷자리 = B

BA에서 AB로 바꾼후 B를 붙힘

그럼 원래는 BA 였음

​

현재 맨뒷자리 A

B에서 A를 붙임

​

그럼 B .

정답.

​

만약 초기 길이가 됐을때 정답을 비교해서 정답이면 1 아니면 0 을 프린트하는 방식으로 구현했다