Boj 25498) 핸들 뭘로 하지

문제

백준 25498

설명

실수하기 좋은 전략 중 하나가 바로 가장 사전순으로 뒤에 오는 자식만을 사용하는 것이다. 만약 두 노드가 같은 알파벳을 가리키면 그 자식까지 가야하고 결국엔 리프노드까지 가서 비교를 수행해야한다. 이 상황에서 string 비교 연산을 그대로 사용하면 시간복잡도가 O(\(\mathrm{N}^2\)) 이 되어서 TLE 가 난다.

이를 간단하게 해결하는 방법은 현재의 Depth 에 한정지어서 문자를 비교를 하고 이에 따라서 탐색을 이어할지 말지를 결정하는 것이다. 아래 코드는 DFS 지만 BFS 를 이용해서도 동일한 작업을 수행할 수 있다. 오히려 BFS 로 푸는 것이 더 직관적이고 더 빠르다.

이런 간단한 방법이 생각보다 생각해내기가 어렵고 실수하기도 좋아 까다로웠다.

시간 복잡도

O(\(\mathrm{N}\))

코드

string in, ans;
vector<int> line[500001];

void DFS(int cur, int parent, int depth = 0)
{
	if (ans.size() == depth)
		ans += in[cur];
	else ans[depth] = in[cur];

	for (auto l : line[cur])
	{
		if (l == parent) continue;
		if (ans.size() == depth || ans[depth + 1] <= in[l])
		{
			if (ans[depth + 1] < in[l]) ans.resize(depth+1);
			DFS(l, cur, depth + 1);
		}
	}
}

int main(void)
{
	int n; cin >> n;
	cin >> in;

	for (int i = 0; i < n - 1; i++)
	{
		int a, b; cin >> a >> b;
		a--, b--;
		line[a].push_back(b);
		line[b].push_back(a);
	}

	DFS(0, -1);
	cout << ans;
}