[백준 12919번] A와 B 2 문제 풀이

 

< 문제 >

 

 

< 입출력 >

 

 

 

 

< TRY1 >

 

처음에는 s에서 t가 될 수 있는 지를 확인했다. 

from collections import deque

s = input()
t = input()

def first_way(s):
    return s+'A'

def second_way(s):
    s += 'B'
    s = ''.join(reversed(s))
    return s

def rotate(s):
    s = ''.join(reversed(s))
    return s

queue = deque()
queue.append(s)

for s in queue:          # 현재의 s나 뒤집은 s가 t에 없으면 만들 수 없으므로 0출력
    queue.pop()
    while len(s) < len(t):
        if first_way(s) in t:
            s = first_way(s)
            if len(s) == len(t):
                print(1)
                exit()
            queue.append(s)

        elif rotate(first_way(s)) in t and len(s) < len(t):
            s = first_way(s)
            queue.append(s)

        elif second_way(s) in t:
            s = second_way(s)
            if len(s) == len(t):
                print(1)
                exit()
            queue.append(s)

        elif rotate(second_way(s)) in t and len(s) < len(t):
            s = second_way(s)
            queue.append(s)

        else:
            print(0)
            exit()

 

 

 

< TRY 2> 

t 에서 s 로 갈 수 있는지 확인한다. 역으로 가야지 시간 초과가 나지 않는다.

s = list(input())
t = list(input())

button = False

def find(t):
    if len(t) == len(s):
        if t == s:
            button = True
        return
    if t[0] == 'B':
        t = t[::-1]
        t.pop()
        find(t)
        t.append('B')
        t = t[::-1]
    if t[-1] =='A':
        t.pop()
        find(t)
        t.append('A')

find(t)

if button:
    print(1)
else:
    print(0)