[boj] 백준 12919 A와 B 2 python 풀이

문제

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

12919번: A와 B 2

 

문제 풀이

bfs나 dfs로 풀이

bfs, dfs 둘 다 S부터 시작하면 시간초과,, T부터 시작해야 연산횟수를 줄일 수 있다. S부터 시작하면 시간초과임.

방문한 지점을 또 방문하는 경우는 없으니 visited는 처리하지 않아도 된다.

 

코드

1) dfs

import sys
input = sys.stdin.readline

S = input().strip()
T = input().strip()

def dfs(word):
    if word == S:
        print(1)
        exit()
    
    if len(S)>len(word):
        return 
    
    if word[-1] == 'A':
        dfs(word[:-1])
    if word[0] == 'B':
        dfs(word[1:][::-1])

if dfs(T) == None:
      print(0)

 

2) bfs

import sys
input = sys.stdin.readline
import collections

S = input().strip()
T = input().strip()

q = collections.deque()
q.append((T))

while q:
    cur_word = q.popleft()
    if cur_word == S:
        print(1)
        break

    for i in range(2):
        n_word = ''
        if i == 0 and cur_word[-1] == 'A':
            n_word = cur_word[:-1]
        if i == 1 and cur_word[0] == 'B':
            n_word = cur_word[1:][::-1]

        if len(S)<=len(n_word):
            q.append(n_word)

else: print(0)