백준 9177 단어 섞기 c++ (bfs)

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

9177번: 단어 섞기

문제

세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.

• 첫 번째 단어 : cat
• 두 번째 단어 : tree
• 세 번째 단어 : tcraete

보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자.

• 첫 번째 단어 : cat
• 두 번째 단어 : tree
• 세 번째 단어 : catrtee

이 경우 역시 가능하다. 그렇다면 "cat"과 "tree"로 "cttaree"를 형성하는건 불가능하다는걸 눈치챘을 것이다.

입력

입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어져 있으며 공백으로 구분된다. 모든 단어는 대문자 또는 소문자로만 구성되어 있다. 세 번째 단어의 길이는 항상 첫 번째 단어와 두 번째 단어의 길이의 합이며 첫 번째 단어와 두 번째 단어의 길이는 1~200이다.

출력

각 데이터집합에 대해 다음과 같이 출력하라.

만약 첫 번째 단어와 두 번째 단어로 세 번째 단어를 형성할 수 있다면

Data set n: yes

과 같이 출력하고 만약 아니라면

Data set n: no

과 같이 출력하라. 물론 n은 데이터집합의 순번으로 바뀌어야 한다. 아래의 예제 출력을 참고하라.

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 문자열
• 그래프 탐색
• 너비 우선 탐색

풀이

dp -> LCS의 흐름으로 문제를 풀다가 풀게 된 문제인데,

dp보단 그래프 탐색으로 풀어야 더 효율적인 것 같아서 dp는 풀이만 생각하고, bfs로 풀었다.

dp를 이용한 풀이는 2차원 배열 bool dp[][]를 두고,

dp[i][j] = 첫 번째 문자열의 i번 인덱스까지, 두 번째 문자열의 j번 인덱스까지 사용했을 때, 사용한 문자만큼의 세 번째 단어의 부분 문자열을 만들 수 있는지 검사하면 된다.

 

bfs를 이용한 풀이는, 

leftIdx == 첫 번째 문자열에서 탐색할 인덱스,

rightIdx == 두 번째 문자열에서 탐색할 인덱스,

findIdx == 세 번째 문자열에서 탐색할 인덱스,

visited[leftIdx][rightIdx] == leftIdx, rightIdx 를 탐색했는지에 대한 여부,

를 두고,

data1[leftIdx] == data3[findIdx]라면 leftIdx와 findIdx를 1씩 더하여 다음 탐색을 이어가고,

data2[rightIdx] == data3[findIdx]라면 rightIdx와 findIdx를 1씩 더하여 다음 탐색을 이어간다.

만약 visited[leftIdx][rightIdx]가 true라면 (leftIdx=a, rightIdx=b 인 경우를 이미 탐색했다면) 스킵하고,

탐색의 종료 조건은 findIdx가 data3의 끝에 다다랐을 때이며, 이는 left와 right가 각각 data1, data2의 끝에 다다랐으며, 성공적으로 첫 번째, 두 번째 문자열을 조건에 맞게 활용하여 세 번째 문자열을 만들었단 의미이다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

string dataSet[3];
bool visited[201][201];
struct info {
	int left, right, findIdx;
};

bool bfs() {
	queue<info> q;
	q.push({ 0,0,0 });
	visited[0][0] = true;
	while (!q.empty()) {
		int left = q.front().left;
		int right = q.front().right;
		int findIdx = q.front().findIdx;
		q.pop();
		if (findIdx == dataSet[2].length()) {
			return true;
		}
		if (left<dataSet[0].length() && dataSet[0][left] == dataSet[2][findIdx] && visited[left+1][right]==false) {
			q.push({ left + 1,right, findIdx + 1 });
			visited[left+1][right] = true;
		}
		if (right<dataSet[1].length() && dataSet[1][right] == dataSet[2][findIdx] && visited[left][right+1] == false) {
			q.push({ left, right + 1, findIdx + 1 });
			visited[left][right+1] = true;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> dataSet[0] >> dataSet[1] >> dataSet[2];
		bool answer =bfs();
		cout << "Data set " << i << ": ";
		if (answer) {
			cout << "yes\n";
		}
		else {
			cout << "no\n";
		}
		memset(visited, false, 201 * 201);
	}
	

	return 0;
}