Boj 3973) Ttl

문제

백준 3973

설명

그래프의 지름문제임.

간단한 풀이 방법은 처음에 아무 지점을 골라서 가장 먼 정점을 찾고, 그 점부터 가장 먼 거리를 구하는 것임.

위 풀이는 그렇게 하지 않고 Back Tracking 을 써서 구함

• 각 정점마다 자기자신과, 자식 노드 중에 가장 먼 노드 간의 길이 중에서 긴 순서대로 2개를 찾음 (자식이 하나면 다른건 0).
• 그 두 값의 합은 그 정점이 그래프의 지름 구할 때의 중앙 이라 가정 시의 지름값이 됨.
• 각 정점마다 수행하므로 진짜 그래프의 중앙에서 최댓값이 나오게 됨.
• 둘중 큰 값은 바로 윗 재귀블럭에서 자기자신과, 그 자식 노드를 지나는 가장 먼 노드의 길이 로써 다시 재사용됨.

이 풀이를 통해서 우리는 한번의 DFS 로 문제를 풀게 됨.

시간 복잡도

O(n)

코드

int n;
vector<int> lines[100001];

int cost, ans, tmp;
int DFS(int cur, int parent, int local_max_cost = 0)
{
	auto node = &lines[cur];
	int max_1 = 0, max_2 = 0, base = cost;

	for (int c : *node)
	{
		if (c == parent) continue;
		cost += 1;
		tmp = DFS(c, cur, cost);
		if (max_1 < tmp - base) { max_2 = max_1; max_1 = tmp - base; }
		else if (max_2 < tmp - base) { max_2 = tmp - base; }
		local_max_cost = max(local_max_cost, tmp);
		cost -= 1;
	}
	ans = max(max_1 + max_2, ans);
	return local_max_cost;
}

int main()
{
	int t, t1, t2;
	cin >> t;
	while (t--)
	{
		cin >> n;
		cost = ans = 0;
		for (int i = 0; i < n; i++)
			lines[i].clear();
		for (int i = 0; i < n - 1; i++)
		{
			cin >> t1 >> t2;
			lines[t1].push_back(t2);
			lines[t2].push_back(t1);
		}
		DFS(0, -1, 0);
		cout << (ans / 2 + ans % 2) << '\n'; // TTL is half of diameter
	}

}