[백준][C++] 9177: 단어 섞기

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

 

유명한 문제입니다. 영어로는 Interleaving string problem 이라고 합니다. interleaving은 끼워넣다 그런 뜻인데요, 문자열 3개가 주어졌을 때 첫 번째 문자와 두 번째 문자를 적절히 섞어서 세 번째 문자를 만들 수 있는지 확인하는 문제입니다. 이때 원래 문자의 순서가 섞이면 안되기 때문에 애너그램(anagram)과는 다릅니다.

leetcode에도 동일한 문제가 있습니다.

 

이 문제는 BFS나 DP로 풀 수 있습니다.

BFS를 예로 들어보겠습니다.

 

먼저 인덱스를 3개 갖고 시작합니다. 각각 첫번째 단어, 두번째 단어, 세번째 단어에서의 인덱스를 나타냅니다. 문자는 각각 a, b, c, 인덱스는 각각 i, j, k라고 하겠습니다.

각각 인덱스 위치의 문자를 확인했을 때 첫 번째 단어의 글자를 넣어야 하는지, 두 번째 단어의 글자를 넣어야 하는지 알 수 있습니다.

 

예를 들어 입력이 cat tree cattree라고 하면, a[i]=='c', b[j]=='t', c[k]=='c' 여기서 보면 첫번째 단어의 글자를 써야겠죠? 그럼 ++i, ++k를 해줍니다. 사실 k=i+j이기 때문에 따로 처리를 해줄 필요는 없습니다.

여기까지만 보면 왜 BFS를 써야하는지 딱히 필요가 없습니다. 그냥 투포인터 알고리즘 돌리면 될 것 같은데요, 경우의 수가 늘어나는 경우가 존재합니다.

예를 들어 cat tree cattree에서 'ca'까지 첫번째 단어에서 뽑아오면 되는 걸 확인했습니다. 그 다음 t를 어디서 뽑아와야 할까요? 첫번째 단어 ca 뒤에 있는 t를 써도 되고, tree의 첫글자 t를 써도 됩니다. 두 경우 다 확인해봐야 하니 BFS가 필요합니다.

 

큐에다가 뭘 넣어야 할까요? 첫 번째 글자의 인덱스와 두 번째 글자의 인덱스를 넣으면 됩니다.

동일한 인덱스 쌍이 큐에 여러번 들어갈 수 있으니 visited 배열 만들어서 체크해줘야 합니다.

 

DP도 원리는 비슷합니다. dp[i][j]: 첫번째 단어의 글자 i개, 두번째 단어의 글자 j개를 썼을 때 만들 수 있는 조합의 개수 or 만들 수 있는지 여부 등으로 짜면 될겁니다 (사실 아직 귀찮아서 안짜봄)

1차원 dp도 될겁니다 (아마)

#include <bits/stdc++.h>
using namespace std;

bool visited[201][201];

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

	int tt;
	cin >> tt;
	for (int i = 1; i <= tt; ++i) {
		string a, b, c;
		cin >> a >> b >> c;

		memset(visited, 0, sizeof(visited));

		auto a_sz=a.size(), b_sz=b.size(), c_sz=c.size();

		if (a_sz+b_sz != c_sz) {
			cout << "Data set " << i << ": no\n";
			continue;
		}

		bool interleaving = false;
		queue<pair<int, int>> q;	// i, j
		q.emplace(0, 0);
		visited[0][0] = true;
		while (!q.empty()) {
			auto [i, j] = q.front();
			q.pop();

			auto k = i + j;
			if (i == a_sz && j == b_sz && k == c_sz) {
				interleaving = true;
				break;
			}

			if (i != a_sz && a[i] == c[k] && !visited[i+1][j]) {
				visited[i + 1][j] = true;
				q.emplace(i + 1, j);
			}
			if (j != b_sz && b[j] == c[k] && !visited[i][j+1]) {
				visited[i][j + 1] = true;
				q.emplace(i, j + 1);
			}
		}

		cout << "Data set " << i << ": " << (interleaving?"yes":"no") << '\n';
	}

	return 0;
}