취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25498번 문제인 핸들 뭘로 하지이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25498 

루트 노드로부터 주어진 트리를 따라 DFS를 진행하며, 기존 정답후보로 찾아둔 문자열과 비교해 사전순으로 더 늦은 문자열을 생성할 수 있다면 해당 문자열을 계속 추적해나가고 그렇지 않다면 해당 방향으로의 탐색을 중단하는 식으로 문제를 해결하자.

문자열의 중간서부터 다른 문자로 교체해 새로운 답의 후보를 얻을 때, 답으로 유지되는 앞부분의 부분문자열을 복사하는 작업을 하면 시간복잡도가 늘어 문제를 해결하기 어려울 것으로 보인다. 해당 부분을 복사하는 대신 새로운 답의 후보에 포함되지 않는 문자를 뒤에서부터 하나씩 지워나가는 식으로 구현하면 시간복잡도가 늘지 않으므로 이렇게 문제를 해결해주자. (하나의 문자를 지우는 작업은 많아야 O(N)번 하게 되기 때문이다.)

아래는 제출한 소스코드이다.

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

int N;
string s;
vector<int> G[500001];
string ans;

void dfs(int cur, int par, int lv) {
	if (ans.length() == lv) ans += s[cur];
	else if (ans[lv] < s[cur]) {
		while (ans.length() > lv) ans.pop_back();
		ans += s[cur];
	}
	else if (ans[lv] > s[cur]) return;

	for (auto& nxt : G[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, lv + 1);
	}
}

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

	cin >> N >> s;
	s = " " + s;

	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	dfs(1, 0, 0);

	cout << ans;
}