[백준 Python] 12919번 A와 B 2

백준 파이썬 12919번 A와 B 2

Gold 5

 

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

import sys
input = sys.stdin.readline
from collections import deque
s = input().rstrip()
t = input().rstrip()
q = deque()
q.append(s)
while q:
    x = q.popleft()
    if (x not in t) and (x[::-1] not in t):
        continue
    if x == t:
        print(1)
        exit()
    q.append(x+"A")
    q.append("B"+x[::-1])
print(0)

간단하게 문자열을 붙여서 풀 수 있는 문제

우선 초기 문자열 S를 q에 넣어준 뒤 기존 상태 혹은 뒤집은 상태가 T의 일부분과 일치하지 않는 경우 continue를 해준다.

그리고 일부가 일치하는 경우 두 가지 연산 1) 문자열 뒤에 A를 추가한다 2) 문자열 뒤에 B를 추가한 뒤 문자열을 뒤집는다를 한 문자열을 q에 넣어준다.