[백준 12919번] A와 B 2 - python

문제 링크

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

12919번: A와 B 2

 

풀이 

처음엔 bfs로 풀이했는데, 메모리 초과가 발생했다.

이후 dfs 백트래킹으로 바꿔 풀이했는데, 시간 초과가 발생하였다.

찾아보니 이 문제의 핵심은

S에서 T로 가능한지 찾는게 아니라, T에서 S가 가능한지 찾아야 한다고 한다. 

S에서 T로 찾으면, 경우의 수가 너무 많아 실패한다고 한다... 

이와 비슷한 문제를 이와 같은 방식이나 bfs로 푼 적이 있는 거 같은데, 어떤 기준인지 모르겠다. 

늘 다양한 방법을 생각하고 시도해보자... 

# 실패한 dfs 코드
def dfs(s, t, cnt):
    global ans 

    if len(s) > len(t):
        return 
    
    if s == t :
        print(1)
        exit(0)
    
    tmp1 = s + 'A'
    dfs(tmp1, t, cnt+1)

    tmp2 = s + 'B'
    tmp2= tmp2[::-1]

    dfs(tmp2, t, cnt+1)


s = input()
t = input()

dfs(s,t,0)
print(0)

조건은 다음과 같다. T에서 S로 가능한지 탐색하는 것이므로 주어진 조건 반대로 탐색해야 한다.

1. T의 맨 뒤가 'A'이면 이를 제거하고, 탐색 

2. T의 맨 앞이 'B'이면 제거하고, 거꾸로 바꿔서 탐색 

양 방향에서 배열에 덧붙이고, 제거하는 것을 편하게 하기 위해서 deque를 사용했다. 

from collections import deque 

def dfs(s, t):
    if len(t) == 0 :
        return

    if s == t :
        print(1)
        exit()
    
    if t[-1] == 'A':
        t.pop()
        dfs(s, t)
        t.append('A')

    if t[0] == 'B':
        t.popleft()
        t.reverse()
        dfs(s,t)
        t.reverse()
        t.appendleft('B')


s = deque(map(str,input()))
t = deque(map(str,input()))

dfs(s,t)
print(0)