BOJ - 단어 섞기 (C++)

문제 출처 : https://www.acmicpc.net/problem/9177

문제 난이도

Gold 5

문제 접근법

처음에 투포인트가 생각났다. 첫 번째 단어 idx랑 두번째단어 idx를 비교해서 세번째단어가 되는지 확인하면 되기 때문이다.
그래서 비슷하지만 BFS를 이용해서 풀었다. 내가 무슨 이야기를 하는지는 다음 풀이를 보면 이해가 갈 듯 하다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 987654321

using namespace std;

bool ch[201][201];

bool isDataSet(string a, string b, string res) {
	memset(ch, false, sizeof(ch));
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	ch[0][0] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int z = x + y;
		q.pop();
		if (x == a.size() && y == b.size() && z == res.size()) return true;
		if (x < a.size() && a[x] == res[z] && !ch[x+1][y]) {
			q.push({ x + 1, y });
			ch[x + 1][y] = true;
		}
		if (y < b.size() && b[y] == res[z] && !ch[x][y+1]) {
			q.push({ x,y + 1 });
			ch[x][y + 1] = true;
		}
	}
	return false;
}


int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		string a, b, ans;
		cin >> a >> b >> ans;
		if (isDataSet(a, b, ans)) {
			cout << "Data set " << i << ": yes\n";
		}
		else cout << "Data set " << i << ": no\n";
	}
	return 0;
}