[PS][BFS] BOJ 9177 : 단어 섞기

[2021년 08월 08일 17시 18분 작성]

[PS][BFS]
BOJ 9177 : 단어 섞기 

 

---

[문제 링크 : 클릭]

---

1. 풀이

분류는 DP 문제였지만, BFS를 통해 해결하였습니다.

 

상태 노드는 int형 정수쌍 {a, b}로 정의합니다. 

{a, b} : str[0]은 a번째 문자를 뽑을 차례이고, str[1]은 b번째를 뽑을 차례 

  --> 이를 기반으로 메모이제이션을 적용해도 됩니다.

 

{0, 0}부터 시작해서 두 개의 문자열 중에 하나를 뽑아 BFS를 진행하며 답을 찾습니다.

+) 분기마다 방문 여부와, 다음 상태 노드가 정답 문자열로 옳게 나아가는지 판단하고,

    a와 b가 각 문자열의 길이를 넘지 않도록 조건을 걸어주었습니다.

 

그러면 현재 노드의 a+b가 str[2]의 길이가 같다면, 정답을 찾은것이므로 yes를 출력합니다.

---

2. 소스코드

[Github 링크 : 클릭]

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

struct P{ int a, b; };

string str[3];

bool GetAnswer()
{
	//만약 첫번쨰 두번째 문자열 길이의 합이 세번째와 같지 않다면
	if(str[0].size() + str[1].size() != str[2].size()) return false;

	queue<P> q;
	bool visited[201][201];
	memset(visited, false, sizeof(visited));

	q.push({0, 0});
	visited[0][0]=true;

	while(!q.empty())
	{
		P curr = q.front();
		q.pop();

		if(curr.a + curr.b == str[2].size()) return true; //찾았으니 true 반환
		
		//다음 상태 노드로 탐색,
		//문자열의 끝, 방문 여부, 다음 상태 노드와 정답 문자열 일치여부 판단
		if(curr.a < str[0].size() && !visited[curr.a+1][curr.b]
			&& str[0][curr.a] == str[2][curr.a+curr.b])
		{
			q.push({curr.a+1, curr.b});
			visited[curr.a+1][curr.b] = true;
		}
		if(curr.b < str[1].size() && !visited[curr.a][curr.b+1]
			&& str[1][curr.b] == str[2][curr.a+curr.b])
		{
			q.push({curr.a, curr.b+1});
			visited[curr.a][curr.b+1] = true;
		}
	}
	return false;
}

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

	int t;
	cin>>t;

	for(int k=0; k<t; k++)
	{	
		for(int i=0; i<3; i++) 
			cin>>str[i];
		
		cout<<"Data set "<<k+1<<": ";

		//세번쨰 문자열을 만들 수 있다면?
		if(GetAnswer())	cout<<"yes\n";
		else cout<<"no\n";
	}

	return 0;
}

---

3. 복기

• 방문 여부를 고려하지 않아 메모리 초과
• 집중력 다소 떨어짐