백준 12919번 A와 B 2 C++ 백트래킹, 재귀, 문자열

리뷰

 

시작 문자열이 특정 조건을 가진 문자열을 더해 도착 문자열로 변할 수 있는지 여부를 체크하는 문제

https://www.acmicpc.net/problem/12919

 

문제 풀이

1. 문자열 a와 b를 입력 받고, b의 크기에서 a크기를 뺀 값을 limit으로 저장한다. 이는 백트래킹의 기저조건이 될 값이다.
2. 변수 flag를 0으로 초기화 하고 함수 bt에 매개변수 0을 전달하여 백트래킹을 시작한다. 이때 0은 재귀 단계를 나타낸다.
3. 백트래킹의 기저조건은 flag가 1일때와 level이 limit에 도달했을 때다, 이는 둘의 문자열의 길이가 동일할때를 의미한다.
4. 문자열 a에서 b로 가는 재귀 말고, 문자열 b에서 a로 가는 재귀를 실행해 줄 것이다.
5. 만약 문자열 b의 앞이 B라면 문자열을 뒤집은 후 맨 뒤의 B를 삭제하고 재귀를 진행해 준다. 재귀 후엔 원복해준다.
6. 만약 b의 맨 뒤 문자열이 A라면 A를 지워주고 재귀를 진행해 준다. 재귀 후엔 원복해 준다.
7. a와 b의 길이가 동일해 졌을때 둘이 같은지를 비교해 주고 같다면 flag를 1로 변환해 준다.
8. flag가 1일 경우 더이상 탐색할 필요가 없기 때문에 모든 재귀를 종료해 준다. 탐색 종료 후 flag를 출력해 준다.

 

참고 사항

flag는 0또는 1이므로 그대로 flag 자체를 출력해 주면 된다.

b에서 a로 진행해 주는 이유는 재귀에 대해 자연적으로 가지치기가 될 수 있기 때문이다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int limit, flag = 0;
string a, b;

void bt(int level) {
	if (flag) return;
	if (level == limit) {
		if (a == b) {
			flag = 1;
			return;
		}
	}
	if (b[0] == 'B') {
		reverse(b.begin(), b.end());
		b.erase(b.end() - 1);
		bt(level + 1);
		b += 'B';
		reverse(b.begin(), b.end());
	}
	if (b[b.size() - 1] == 'A') {
		b.erase(b.end() - 1);
		bt(level + 1);
		b += 'A';
	}
}

int main() {
	cin >> a >> b;
	limit = b.size() - a.size();
	bt(0);
	cout << flag;
}