[백준] 12919번 A와 B 2 - Python / 알고리즘 중급 1/3 - 그리디 알고리즘 (도전)

ByungJik_Oh·2025년 6월 29일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

173/244

💡 문제

수빈이는 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을 출력한다.

💭 접근

이 문제는 12904번 A와 B 문제와 많이 유사하다. s에서 t로 가는 것이 아닌 t에서 s로 주어진 규칙에 따라 반대로 가면 되는 문제이다. 그러나 다른 점이 하나 있는데, 경우의 수를 나누어 살펴보자.

t의 첫번째 알파벳이 B가 아니고 마지막 알파벳이 A인 경우

이 경우에는 그대로 마지막 A만 제거해주면 된다.
t의 첫번째 알파벳이 B이고 마지막 알파벳이 A가 아닌 경우

이 경우에는 문자열을 뒤집은 뒤, 마지막 B를 제거해주면 된다.
t의 첫번째 알파벳이 B이고 마지막 알파벳이 A인 경우

이 경우에는 두가지 경우가 동시에 존재할 수 있는데,
1번과 같이 마지막 A만 제거하는 방법과, 2번과 같이 문자열을 뒤집은 후, 마지막 B를 제거하는 방법이 동시에 가능하다. 따라서 이 두가지 경우를 모두 동시에 고려해주어야 한다.

따라서 위 세가지 방법을 모두 고려하기 위해선 백트래킹을 사용하여 t의 알파벳을 주어진 규칙에 따라 제거한 뒤, s와 길이가 같아졌을 때 s와 같은지 판단해주면 해결된다.

📒 코드

import sys

def dfs(word, depth):
    if depth == len(s):
        if word == s:
            print(1)
            sys.exit()
        return

    if word[0] != 'B' and word[-1] == 'A':
        next = word[:depth - 1]
        dfs(next, depth - 1)
    elif word[0] == 'B' and word[-1] != 'A':
        next = word[::-1][:depth - 1]
        dfs(next, depth - 1)
    elif word[0] == 'B' and word[-1] == 'A':
        next = word[:depth - 1]
        dfs(next, depth - 1)
        next = word[::-1][:depth - 1]
        dfs(next, depth - 1)

s = input()
t = input()

dfs(t, len(t))

print(0)