12919번 맞힌 사람

📌Problem

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

✍solution

(dfs 활용 - 시간초과)

• dfs를 통해 시작점 s부터 조건에 맞는 t 길이까지 조건에 맞는 문자 만들어 비교하여 문제를 해결
• (시간 초과 이유) s의 길이부터 t 길이까지 모든 경우의 문자를 확인
  (dfs - 정답)
• t부터 s로 가는 방법을 조건에 따라 재귀 통해 찾아가는 방식으로 변경
• 조건1) 문자열의 뒤에 A를 추가 -> 문자의 맨뒤가 A
• 조건2) 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다 -> 문자의 맨앞이 B

💻Code

(오답 코드-시간초과)

def dfs(level, word):
    global s,t,check
    if check != 0:
        return
    if level==len(t):
        if word == t:
            check=1
        return
    dfs(level+1, word+'A')
    dfs(level+1, (word+'B')[::-1])

s=input()
t=input()
check=0
dfs(len(s), s)
print(1) if check==1 else print(0)

(정답 코드)

def dfs(level, word):
    global s,t,check
    if check != 0:
        return
    if level==len(s):
        if word == s:
            check=1
        return
    if word[-1]=='A':
        dfs(level-1, word[:-1])
    if word[0]=='B':
        dfs(level-1, word[1:][::-1])

s=input()
t=input()
check=0
dfs(len(t), t)
print(1) if check==1 else print(0)

💡Takeaway

• 재귀 문제를 풀때는 최소한의 경우를 찾아 갈 수 있게 코드를 짜는 것이 중요
• 재귀는 예외처리가 하나라도 부족하면 계산하는 양이 많아짐
• 목적지에 도달하는 문제의 경우 역순으로 푸는 것을 고려해야함