[BOJ/C++] 1967(트리의 지름)

1. Link

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

2. 풀이 과정

1. 트리에 존재하는 경로들 중 가장 긴 것의 길이 -> 탐색(DFS, BFS)

• DFS가 정해라고는 생각하고 실제로 DFS로 풀면 시간적으로 이득을 많이 볼 수 있습니다. 다만 BFS가 구현이 쉽기 때문에 BFS와 DFS 모두 구현해서 풀었습니다.

• 이 문제에서 고전한 경험이 있다면, 아마 이 내용이 도움이 되길 바라며 작성해봅니다.

1. 우선, 끝과 끝의 길이를 계산해야 합니다. 리프 노드 간 거리 계산을 위해서는 상위 노드를 거치고 결국 그 상위 노드들의 가중치도 가져갈 수 있기 때문에 단말 노드 간의 경로만 생각해주면 될 법 합니다.

2. 문제의 조건을 살펴보면, 트리의 노드 번호가 정해지는 순서는 상위 노드의 2배, 2배 + 1의 형태입니다. 그러므로
   ((n / 2) + 1)번 노드부터 n번 노드를 지름의 한 점으로 삼는 경우를 전부 탐색하면 됩니다.

3. 이후로는 각 노드를 탐색한 후, 최대값 갱신을 통해 트리의 최대 지름 구할 수 있습니다.

3. 정답 코드(BFS, DFS)

1. BFS

//1. BFS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define p pair<int, int>

int n, answer = 0;
vector<p> v[10001];
bool vis[10001];

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

void bfs(int i) {
	queue<p> q;
	q.push({ i, 0 });
	vis[i] = 1;
	while (!q.empty()) {
		p cur = q.front(); q.pop();
		for (p nxt : v[cur.first]) {
			if (vis[nxt.first]) continue;
			vis[nxt.first] = 1;
			int next = cur.second + nxt.second;
			q.push({ nxt.first, next });
			if (answer < next) answer = next;
		}
	}	
}

void solution() {
	input();
	for (int i = (n >> 1) + 1; i <= n; ++i) {
		memset(vis, 0, sizeof(bool) * (n + 1));
		bfs(i);
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

2. DFS

//2. DFS
#include <iostream>
#include <vector>
using namespace std;
#define p pair<int, int>

int n, answer = 0;
vector<p> v[100001];
bool vis[100001]{ 0 };

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

void dfs(int i, int dist) {
	if (answer < dist) answer = dist;
	for (p nxt : v[i]) {
		if (vis[nxt.first]) continue;
		vis[nxt.first] = 1;
		dfs(nxt.first, dist + nxt.second);
		vis[nxt.first] = 0;
	}
}

void solution() {
	input();
	for (int i = (n >> 1) + 1; i <= n; ++i) {
		vis[i] = 1;
		dfs(i, 0);
		vis[i] = 0;
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

1. (BFS)
   
2. (DFS)