백준 12919 A와 B 2 문제 해결 전략

문제 개요

백준 12919번 문제는 두 문자열 S와 T가 주어졌을 때, S를 T로 변환할 수 있는지를 판단하는 문제입니다. 이 변환 과정에서 사용할 수 있는 규칙은 두 가지입니다.

첫 번째 규칙은 문자열의 뒤에 ‘A’를 추가하는 것이고, 두 번째 규칙은 문자열을 뒤집고 그 앞에 ‘B’를 추가하는 것입니다. 이러한 규칙을 활용하여 문자열 S를 T로 변환할 수 있는지를 판단하는 것은 단순한 문자열 조작을 넘어, 알고리즘적 사고를 요구하는 문제입니다.

이 문제는 특히 변환 과정을 거꾸로 생각하는 것이 핵심입니다. 즉, T에서 S로 변환하는 과정을 탐색하는 방식으로 접근할 수 있습니다.

이 과정에서 사용할 수 있는 방법은 재귀적 깊이 우선 탐색(DFS)입니다. 이를 통해 가능한 모든 변환 경로를 탐색하고, S와 T가 같은지를 판단하게 됩니다.

접근 방법

문제를 해결하기 위한 접근 방식은 T에서 S로 가는 방향으로 생각하는 것입니다. T에서 S로 변환하는 규칙은 다음과 같습니다.

1. T의 끝이 ‘A’이면 A를 제거할 수 있습니다.
2. T의 시작이 ‘B’이면 B를 제거하고 T를 뒤집을 수 있습니다.

이 두 가지 규칙을 통해 T를 S로 변환할 수 있는지를 검사합니다. 문자열 T의 다양한 상태에 따라 이 규칙을 적용해가면서 S와 일치하는 경우를 찾게 됩니다.

이러한 접근은 탐색 공간을 줄이고, 불필요한 경우의 수를 배제할 수 있어 효율적입니다. 다음은 S와 T의 변환 과정을 정리한 표입니다.

변환 단계	S	T	적용 규칙
초기 상태	“A”	“ABBA”	–
1단계	“A”	“AB”	T의 끝이 ‘A’이므로 A 제거
2단계	“A”	“B”	T의 시작이 ‘B’이므로 B 제거 및 뒤집기
3단계	“A”	“”	T가 비어있음

위 표에서 볼 수 있듯이, T에서 S로 변환하기 위해서는 T의 마지막 문자를 제거하거나, T의 첫 번째 문자를 제거한 후 뒤집는 과정을 반복해야 합니다. 이 과정에서 S와 T가 같아지는 경우가 발생하면 1을 출력하고, 모든 가능성을 다 따져봤음에도 S와 T가 같아지지 않는 경우에는 0을 출력하게 됩니다.

다른 내용도 보러가기 #1

코드 구현

문제 해결을 위한 코드는 다음과 같은 방식으로 구성됩니다. 먼저 입력받은 문자열 S와 T를 리스트 형태로 변환한 후, 재귀 함수를 통해 T에서 S로 변환할 수 있는지를 검사합니다.

“`python
import sys

def dfs(t):
if t == s:
print(1)
sys.exit()
if len(t) == 0:
return

if t[-1] == 'A':
    dfs(t[:-1])  # T의 끝이 'A'일 경우 제거
if t[0] == 'B':
    dfs(t[::-1][:-1])  # T의 시작이 'B'일 경우 제거하고 뒤집기

s = list(input().strip())
t = list(input().strip())
dfs(t)
print(0)
“`

위 코드에서는 dfs라는 재귀 함수를 정의하여 T의 상태에 따라 S와 비교하게 됩니다. 만약 T의 상태가 S와 같아지는 경우, 즉 t == s일 때는 1을 출력하고 프로그램을 종료합니다.

T의 길이가 0이 되는 경우는 더 이상 변환할 수 있는 경우가 없음을 의미하므로, 이 경우에는 함수를 종료합니다. 이와 같은 방식으로 문자열 변환 문제를 해결하는 것은 알고리즘적 사고를 기를 수 있는 좋은 연습이 됩니다.

특히 DFS와 같은 탐색 알고리즘을 활용하여 문제를 해결하는 경험은 프로그래밍 능력을 한층 더 향상시킬 수 있습니다.

예제 및 시나리오

다양한 입력에 대한 시나리오를 통해 문제를 더욱 깊이 이해할 수 있습니다. 예를 들어, 문자열 S가 “A”, T가 “ABBA”인 경우를 생각해 보겠습니다.

1. 입력:
2. S: “A”

3. T: “ABBA”

4. 변환 과정:

5. T의 끝이 ‘A’이므로, A를 제거하여 “ABB”로 만듭니다.
6. T의 시작이 ‘B’이므로, B를 제거하고 T를 뒤집어 “BA”로 만듭니다.
7. T의 끝이 ‘A’이므로, A를 제거하여 “B”로 만듭니다.
8. T의 시작이 ‘B’이므로, B를 제거하여 “”로 만듭니다.

이와 같은 방식으로 모든 변환 과정을 시뮬레이션할 수 있으며, 최종적으로 S와 T가 같아지는 경우를 찾는 것이 이 문제의 목표입니다.

문자열 상태	현재 T	S	결과
초기 상태	“ABBA”	“A”	–
1단계	“ABB”	“A”	–
2단계	“BA”	“A”	–
3단계	“B”	“A”	–
최종 상태	“”	“A”	0

위 표에서 볼 수 있듯이, 최종적으로 T가 비어있게 되었고, S와 T가 같지 않으므로 0을 출력하게 됩니다.

결론

백준 12919 A와 B 2 문제는 문자열 변환 문제로, 알고리즘적 사고를 통해 해결할 수 있는 흥미로운 예제입니다. S에서 T로의 변환이 아니라, T에서 S로의 변환이라는 관점으로 접근하는 것이 핵심입니다.

이 과정에서 DFS와 같은 알고리즘을 활용하여 효율적으로 문제를 해결할 수 있습니다. 이러한 문제를 통해 문자열 처리와 재귀적 사고를 기를 수 있으며, 실제 프로그래밍에서 자주 겪는 문제를 해결하는 데 큰 도움이 될 것입니다.

연습을 통해 다양한 변형 문제를 접해보는 것도 좋은 학습 방법입니다.

관련 영상

같이 보면 좋은 글