boj, 백준) 9177. 단어 섞기 (C / C++)

1. 문제 링크

www.acmicpc.net/problem/9177

9177번: 단어 섞기

2. 문제 개요

세 개의 단어가 주어졌을 때, 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 계산하는 프로그램을 만들어보자.

 

3. 문제 힌트

완전탐색을 하면 어떻게 될까..?

aaab aaac aaabaaac이 입력으로 주어지고, 세 번째 단어인 aaabaaac의 왼쪽 끝에서 오른쪽 끝으로 탐색을 한다고 해보자.

 

첫 번째 a는 "aaab"의 a인지, "aaac"의 a인지 알 방법이 없다. 즉, 끝까지 찾아보지 않는 한 결정할 수 없다.

그래서, 2갈래로 나뉘게 되고, aaab의 a라고 가정하고 탐색을 이어나가는 것과 aaac의 a라고 가정하고 탐색을 이어나가는 방법이 있다.

 

이렇게 되면 경우의 수가 기하급수적으로 늘어나게 되어 시간 초과가 날 것이다.

어떻게 하면 이런 중복적인 부분을 제거하면서 빠른 시간에 문제를 해결할 수 있을까?

 

또, 모든 순열을 만들어서 비교하는 그런방법은 당연히 시간 초과다.

 

4. 문제 풀이

문제의 분류를 봤을 때, BFS라고 되어있는데 굳이 그래프 탐색을 비유하자면 DFS 쪽에 가깝지 않을까 싶다. (개인적인 생각) 결국 완전 탐색을 DP와 섞어서 DFS형태로 하기 때문에..

 

각 단어의 index를 나타내 줄 변수 세 개를 선언하자.

모두 단어의 첫 번째 알파벳을 가리킨다.

그래서, 세 번째 단어가 가리키는 알파벳과 첫 번째 단어가 가리키는 알파벳이 같고, 두번째 단어가 가리키는 알파벳과 다르다면 그때는 세번째 단어가 가리키는 알파벳이 첫번째 단어라고 결정지을 수 있다. (이게 무슨 말????)( 99.99% 이해가 완벽하게 안 될 것 같지만, 이 부분은 코드를 보면 잘 알 수 있을 것이라고 생각합니다.)

 

단어 입력을 받고 마지막에 끝을 나타내는 단어 '.'을 추가해주었다.

길이가 200인 단어가 들어왔을 때, 탐색을 마무리 지으면 index가 200을 가리키고 배열 크기를 초과해서 런타임 에러가 날 수 있기 때문이다.

 

'어떠한 상태'를 memoization 해야 한다. [첫 번째 단어 인덱스][두 번째 단어 인덱스]로 나타낼 수 있다. 세번째 단어는 첫번째 + 두번째 인덱스로 결정되어버리기 때문에 갖고 있을 필요가 없다.

 

(3) 문제 힌트에서 말했던 것처럼 계속 2갈래로 나뉘게 되면 봤던 것을 또 보는 그런 상황이 오기 때문에 상태를 저장해야 한다. 상태는 특별한 것이 없고 그냥 방문했는지 안 했는지만 나타내면 된다.

(1->2->4->...로 늘어나는걸 2->2->2->..로 방문을 표기함으로써 제한한다. )

 

 

5. 코드

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

bool cache[201][201];
string first, second, third;

//Findex -> the index of 'F'irst string
bool dp(int Findex, int Sindex, int Tindex)
{
	if (Tindex == third.length())
		return true;

	if (cache[Findex][Sindex])
		return false;

	cache[Findex][Sindex] = true;
	if (third[Tindex] == first[Findex] && third[Tindex] == second[Sindex])
	{
		return dp(Findex + 1, Sindex, Tindex + 1) || dp(Findex, Sindex + 1, Tindex + 1);
	}
	else if (third[Tindex] == first[Findex])
	{
		return dp(Findex + 1, Sindex, Tindex + 1);
	}
	else if (third[Tindex] == second[Sindex])
	{
		return dp(Findex, Sindex + 1, Tindex + 1);
	}
	else
	{
		return false;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	
	for (int i = 1; i <= t; ++i) {
		cin >> first >> second >> third;
		memset(cache, false, sizeof(cache));
		first.push_back('.');
		second.push_back('.');
		bool ans = dp(0, 0, 0);

		if (ans)
			cout << "Data set " << i << ": yes\n";
		else
			cout << "Data set " << i << ": no\n";
	}


	return 0;
}

6. 결과