백준 - 12919번 : A와 B 2 (C++)

풀이 방법 : 브루트 포스

A를 주어진 조건대로의 연산으로 B를 만들 수 있는지 하는 문제이다.
만약 A에서 주어진 연산 두 가지를 계속 적용시켜가면서 연산을 하면 따지게 되는 경우의 수가 너무 많아져서 시간 혹은 메모리 초과가 날 것이다.

반대로 B에서 주어진 연산을 거꾸로 적용시켜가면서 진행하면 따지게 된다면, 현재 문자열의 마지막 글자가 'A'가 아닌 경우는 1번 연산을 적용한 결과값일 수 없다는 것이고, 첫글자가 'B'가 아닌 경우는 2번 연산을 적용한 결과값일 수 없다는 것이므로, 따져야하는 경우의 수를 줄일 수 있다.

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

unordered_set<string> Check;

bool IsEnable = false;

void DFS(string Current, string Dest)
{
	if (IsEnable)
		return;

	int CurLength = Current.length();
	int DestLength = Dest.length();

	if (CurLength == DestLength)
	{
		if (Current == Dest)
		{
			IsEnable = true;
		}

		return;
	}

	int Size = Current.length();
	
	if (Current[Size - 1] == 'A')
	{
		string Next = Current.substr(0, Size - 1);

		if (Check.find(Next) == Check.end())
		{
			Check.insert(Next);
			DFS(Next, Dest);
		}
	}

	if (Current[0] == 'B')
	{
		string Next = Current.substr(1, Size);
		int NextLength = Next.length();

		for (int i = 0; i < NextLength / 2; ++i)
		{
			char Temp = Next[i];
			Next[i] = Next[NextLength - i - 1];
			Next[NextLength - i - 1] = Temp;
		}

		if (Check.find(Next) == Check.end())
		{
			Check.insert(Next);
			DFS(Next, Dest);
		}
	}

}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	
	string S, T;
	cin >> S >> T;
	
	DFS(T, S);

	cout << (int)IsEnable;
}

여기서는 혹시 몰라서 unordered_set에 중간 결과 문자열들을 저장시켜가면서 중복 체크를 더 줄이려고 했는데 이 부분을 빼더라도 충분히 통과는 하더라