백준 12919 A와 B 2 (C++)

12919번: A와 B 2

재귀를 이용하는 문제이다. 주어진 S가 T가 될 수 있는지 알아야 한다. S에서 재귀를 통해 찾아가면 너무 많은 경우의 수가 생기므로 T에서 S를 찾아가는 방식을 이용하였다. 제거하는데 있어서 3가지 경우의 수가 있다.

• 맨 앞과 뒤가 A일 경우
• 맨 앞과 뒤가 B일 경우
• 맨 앞이 B, 맨 뒤가 A 일 경우

첫번째와 두번째는 각각 조건에 맞춰 dfs를 돌려주면 된다. 세번째의 경우 A를 제거하거나 뒤집어서 B를 제거하는 두가지 방식을 각각 사용하여 dfs를 돌려주었다. 이 후 S와 같아지면 1을 출력해주었다.
어렵지 않게 풀 수 있었던 문제였다. 처음 S에서 시작하여 T를 찾으려하니 시간 초과가 발생했었고 바로 반대로 찾는 방식을 생각해내 문제를 풀 수 있었다. 문자열을 이용하는 문제들을 좀 더 풀어봐야 겠다.

#include <iostream>
#include <algorithm>

using namespace std;

string S, T;
bool result;

void dfs(string now) {
	if (result) return;
	if (S == now) {
		result = true;
		return;
	}
	if (S.size() >= T.size()) return;

	string tmp = now;
	if (tmp[0] == 'B' && tmp.back() == 'B') {
		reverse(tmp.begin(), tmp.end());
		tmp.pop_back();
		dfs(tmp);
	}
	else if (tmp[0] == 'A' && tmp.back() == 'A') {
		tmp.pop_back();
		dfs(tmp);
	}
	else if (tmp[0] == 'B' && tmp.back() == 'A') {
		tmp.pop_back();
		dfs(tmp);

		tmp = now;
		reverse(tmp.begin(), tmp.end());
		tmp.pop_back();
		dfs(tmp);
	}
	else return;
}

void solution() {
	dfs(T);

	cout << result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> S;
	cin >> T;

	solution();
	
	return 0;
}