[백준 12904] A와 B (C++)

문제 링크: https://www.acmicpc.net/problem/12904

12904번: A와 B

1. 주의할 점

- Set + DFS/BFS로 시도시 메모리 초과 발생 가능

 

2. 구현

(1) Set + BFS : 메모리 초과

- 현재 Queue의 Front에 담긴 문자열을 기준으로 뒤에 'A' 추가 or 뒤집기 + 'B' 추가 시도하며, 해당 문자열이 이미 셋에 존재한다면 큐에 넣지 않는다

- BFS는 First==Second 혹은 First의 길이가 Second와 같을 경우 중단한다

#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
set<string> s;
queue<string> q;

void add(string temp) {
	s.insert(temp);
	q.push(temp);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int result = 0;
	string first, second, temp;
	cin >> first >> second;
	s.insert(first);
	q.push(first);

	while (!q.empty()) {
		string ss = q.front();
		q.pop();
		int len = ss.size();
		if (ss == second) {
			result = 1;
			break;
		}
		if (len >= second.size()) continue;
		//뒤에 A추가
		temp = ss + 'A';
		if (s.find(temp) == s.end())	add(temp);
		//뒤집고 뒤에 B추가
		reverse(ss.begin(), ss.end());
		ss += 'B';
		if (s.find(ss) == s.end())	add(ss);
	}
	cout << result;
	return 0;
}

 

(2) 그리디

- Second를 통해 First를 유추한다

- Second의 마지막 문자가 'A'라면 A 제거

- Second의 마지막 문자가 'B'라면 B 제거 후, 뒤집기

- While문은 Second의 길이가 First보다 클때까지만 수행한다

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string first, second, temp;
int result = 0;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> first >> second;
	int flen = first.size();
	int slen = second.size();
	while (slen > flen) {
		char c = second[slen - 1];
		//뒤 A 삭제
		if (c == 'A') {
			second = second.substr(0, slen - 1);
		}
		//뒤 B삭제 후 뒤집기
		else {
			second = second.substr(0, slen - 1);
			reverse(second.begin(), second.end());
		}
		slen--;
	}
	if (first == second) result = 1;
	cout << result;
	return 0;
}