BOJ 3409 - Word equations(문자 방정식)

다소 까다로운 문제다. 문제 내용을 읽으면 우선 트리를 떠올리게 되는데, 문제에 맞는 트리의 속성을 적자면 아래와 같다.

1. 이진 트리다.

2. 자식이 하나만 있는 노드는 없으며, 자식이 있다면 무조건 2개의 자식을 갖는다.

하지만, 트리는 아니다. 이는 훼이크고, 그냥 단순 그래프이나, 노드에 순서성에 대해 트리형태처럼 보일 뿐이다.

정확히는 DAG(Directed acyclic graph)를 나타낸다.

따라서 나는 세 단계를 거쳐 AC를 받게 됐다.

1. MLE

2. TLE

3. AC

(만약 단순 솔루션만 보고 싶다면 기본 아이디어 이후, 3.으로 바로 넘어가길 바란다.)

* 기본 아이디어

  그래프를 배열로 구현하고, 문자열에 대한 것은 string, map을 사용하여 배열에 대한 위치값(또는 포인터 값을 지정)을 지정하고 변수 T에 해당하는 노드로 바로 해싱할 수 있도록 구성하고, 그 노드의 자식 노드가 있다면 방문하여 패턴 P를 만들 수 있는지 확인해준다.

1. MLE (Memory limit exceeded)

   단순 그래프를 구성한 뒤, 해당하는 노드에 string 변수를 넣어, 자식을 순회하며 합치는 방식을 했다. 가령 부모 노드가 두 자식 노드를 가지고 있으며 두 자식 노드가 각각 "aaa", "bbb"를 가지고 있었다면, 순회 반환 값으로 aaabbb를 내보낸다.

   최악의 경우 그래프 구성이 일직선으로 연달아 구성되는 그래프로 구성될 수 있으며, 이럴 경우 (아마) 최대 500개 노드에 대해서 순회를 할 때, 250개의 자식 노드가 5글자씩 가지고 있다고한다면, 순회할 때 루트가 반환하는 문자열의 길이는 2500가 되며, 이 때 순회하면서 생성된 string 변수들의 크기는 총 10+15+ ... + 2500 = 약 5*500*501/2 = 626250(약 612KB)가 되므로 테스트케이스도 얼마나 있는지 모르는데, 메모리를 너무 많이 사용하게 된다. 게다가 한 번만 쓰고 버리기 때문에 낭비가 아닐 수 없다.

#include <iostream>
#include <string>
#include <cstring>
#include <map>
using namespace std;
struct _d {
	string str;
	bool divi = 0;
	int lc=0, rc=0;
};
_d tree[501];
int gpos(map<string, int>& pool, string s, int& size) {
	if (pool[s] == 0)
		pool[s] = ++size;
	return pool[s];
}

string build(_d node) {
	if (node.divi)
		return build(tree[node.lc]) + build(tree[node.rc]);
	return node.str;
}

int main() {
	int tc, K, i, pos,tsize,pa,lc,rc,tp,pp, L;
	char P[2001], equation[30], *t;
	string T, eq[5], res;
	cin >> tc;
	while (tc--) {
		map<string, int> pool;
		tsize = 0;
		cin >> K;
		getchar();
		for (i = 0; i < K; i++) {
			pos = 0;
			
			fgets(equation, 30, stdin);
			equation[strlen(equation) - 1] = 0;

			t = strtok(equation, " ");
			do {
				eq[pos++] = t;
				t = strtok(NULL, " ");
			} while (t != NULL);
			if (pos == 5) {
				pa = gpos(pool, eq[0], tsize);
				tree[pa].lc = gpos(pool, eq[2], tsize);
				tree[pa].rc = gpos(pool, eq[4], tsize);
				tree[pa].divi = 1;
			}
			else {
				pa = gpos(pool, eq[0], tsize);
				tree[pa].str = eq[2];
				tree[pa].divi = 0;
			}
		}		
		cin >> T >> P;
		res = build(tree[gpos(pool, T, tsize)]);		
		L = strlen(P);
		tp = pp = 0;
		while (tp < res.size() && pp < L) {
			if (res[tp] == P[pp]) pp++;
			tp++;
		}
		cout << (pp == L ? "YES" : "NO") << '\n';
	}
	return 0;
}

2. TLE (Time limit exceeded)

  그래서 순회한 것을 반환하지 않고, 단말 노드일 때만 방문하여 brute-force로 문자열을 비교한다. 패턴 P에 대해 처음부터 끝까지 읽어들이며, 단말노드의 문자열을 다 비교하거나, P를 다 비교했다면 종료하는 식이다. 이렇게하면 일일히 문자열을 반환하지 않기 때문에, 최대 5*250 = 1250(약 1KB)로 테스트케이스가 1024*128개 정도여도 충분히 수행할 수 있는 용량이 된다.

#include <iostream>
#include <string>
#include <cstring>
#include <map>
using namespace std;
struct _d {
	string str;
	bool divi = 0;
	int lc=0, rc=0;
};
_d tree[501];
int gpos(map<string, int>& pool, string s, int& size) {
	if (pool[s] == 0)
		pool[s] = ++size;
	return pool[s];
}
char P[2011];
int pp, L;
void build(const _d& node) {
	if (node.divi) {
		if (pp < L) build(tree[node.lc]);
		if (pp < L) build(tree[node.rc]);
	}
	else {
		for (int i = 0; i < node.str.size() && pp < L; i++)
			if (P[pp] == node.str[i]) pp++;
	}
}

int main() {
	int tc, K, i, pos,tsize,pa;
	char equation[30], *t;
	string T, eq[5], res;
	cin >> tc;
	while (tc--) {
		map<string, int> pool;
		tsize = 0;
		cin >> K;
		getchar();
		for (i = 0; i < K; i++) {
			pos = 0;
			
			fgets(equation, 30, stdin);
			equation[strlen(equation) - 1] = 0;

			t = strtok(equation, " ");
			do {
				eq[pos++] = t;
				t = strtok(NULL, " ");
			} while (t != NULL);
			if (pos == 5) {
				pa = gpos(pool, eq[0], tsize);
				tree[pa].lc = gpos(pool, eq[2], tsize);
				tree[pa].rc = gpos(pool, eq[4], tsize);
				tree[pa].divi = 1;
			}
			else {
				pa = gpos(pool, eq[0], tsize);
				tree[pa].str = eq[2];
				tree[pa].divi = 0;
			}
		}
		
		cin >> T >> P;
		L = strlen(P);
		pp = 0;
		build(tree[gpos(pool, T, tsize)]);
		cout << (pp == L ? "YES" : "NO") << '\n';
	}
	return 0;
}

3. AC(Aceepted)

  하지만 시간 초과..

  이유는 즉, 실패한 노드에 대해서 다시금 방문해야할 때 그 P의 비교 위치가 그대로 일 수도 있다는 점이다. 무슨 말이냐면 서로 다른 두 노드에 대해 각 노드가 하나의 단말 노드를 가리키고 있다면 발생한다.

  예를 들어, input이 아래와 같았을 때 그래프는 아래 그림처럼 그려진다.

...

T = A + B

A = C + D

B = D + E

C = abc

D = fgh

E = ik

T

kkkiii

answer : NO

  보면 D노드에 대해 A도 참조하고, B도 참조한다. 패턴이 "kkkiii"이기 때문에 단말 노드 방문할 때 A->C->D->B->C->D 순을 거친다. 따라서 C노드에 대해선 맞는 문자가 없으므로 바로 나오고, D 역시 바로 나오게 된다. 하지만 B가 다시금 D를 참조하게 되는데, 현재 일치한 문자가 없음에도 코드는 D를 방문하게 된다. 즉 현재 확인해야하는 패턴 P의 위치를 y라고할 때, y위치에서 한 번 실패한 노드에 대해서 y위치에 대해 다시 매칭하고자 그 실패했던 노드를 다시 확인할 필요가 없다는 것이다. 

  위의 입력에서는 A에서 패턴 P에 대해 D노드가 실패했음을 알았으니, B가 D를 패턴 P의 y위치에 대해 매칭하고자 방문할 이유가 없다는 것이다.

  i) 노드 D를 처음 처리한 후

P = "ik"

y = 0

  ii) 노드 A를 모두 처리한 후

P = "ik"

y = 0

  

따라서 A를 모두 처리하고 나더라도 패턴 P에 매칭된 문자가 없었기 때문에 y=0을 고수하고 있고, 이 상태에서 B를 방문하게 되는데 제일 먼저 노드 D를 방문하게 됩니다. 따라서 y=0에 대해 노드 D를 이미 방문했기 때문에 바로 E로 넘어가게 만드는 것입니다. 

  위 과정을 처리해주지 않으면 패턴 P의 같은 위치 y에 대해 같은 노드를 수없이 많이 반복할 수 있기 때문에 이를 memoization을 통해 위치 y에 대해 해당 노드를 방문했었는지를 저장해줍니다. 이는 단말노드 뿐만 아니라 자식을 가지는 노드도 마찬가지입니다. 

T = A+A 일 경우를 생각해보면 간단합니다.

  따라서 노드마다 동적 계획법을 사용하기 위해 메모리 공간을 잡아줍니다. 공간 크기는 패턴 P의 길이면 됩니다. 그리고 동적 계획법에 대해 나올 수 있는 값이 0~strlen(P)-1이기 때문에 초기설정 값을 -1 정도로 잡아줍니다.

#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <vector>
using namespace std;

int L, tc;
struct _d {
	string str;
	bool divi = 0;
	_d *lp, *rp;
	vector<int> dp;
	int ttc=-1;
	int build(const string& p, int pp) {
		if (dp.empty()) dp.resize(p.length() + 1, -1);
		if (dp[pp] < 0) {
			if (divi)
				return dp[pp] = rp->build(p, lp->build(p, pp));
			else {
				for (int i = 0; i < str.size() && pp < L; i++)
					if (p[pp] == str[i]) pp++;
				return pp;
			}
		}
		else return dp[pp];
	}
};


int gpos(map<string, int>& pool, string s, int& size) {
	if (pool[s] == 0)
		pool[s] = ++size;
	return pool[s];
}

int main() {
	int K, i, tsize,pa;
	char equation[30], *t;
	string T, eq[3], res, P;
	cin >> tc;
	while (tc--) {
		_d tree[501];
		map<string, int> pool;
		tsize = 0;
		cin >> K;
		getchar();
		for (i = 0; i < K; i++) {
			cin >> eq[0] >> eq[2] >> eq[1];
			if (eq[1][0] <= 'Z') {
				cin >> eq[2] >> eq[2];
				pa = gpos(pool, eq[0], tsize);
				tree[pa].lp = &tree[gpos(pool, eq[1], tsize)];
				tree[pa].rp = &tree[gpos(pool, eq[2], tsize)];
				tree[pa].divi = 1;
			}
			else {
				pa = gpos(pool, eq[0], tsize);
				tree[pa].str = eq[1];
				tree[pa].divi = 0;
			}
		}		
		cin >> T >> P;
		L = P.length();
		cout << (tree[gpos(pool, T, tsize)].build(P, 0) == L ? "YES" : "NO") << '\n';
	}
	return 0;
}