트리의 지름 (feat. 백준, 1167번)

트리의 지름
https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
map<int, set<pair<int, int>>> tree;
bool visit[100001];
int dp[100001];
void bfs(register int n) {
	queue<int> q;
	q.push(n);
	visit[n] = true;
	while (!q.empty()) {
		auto x = q.front(); q.pop();
		for (auto iter = tree[x].begin(); iter != tree[x].end(); ++iter) {
			register int y = iter->first, w = iter->second;
			if (!visit[y])
				visit[y] = true, dp[y] = max(dp[y], dp[x] + w), q.push(y);
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int V;
	cin >> V; 
	for (register int v = 0, x, y, w; v < V; ++v) {
		cin >> x;
		while (1) {
			cin >> y;
			if (y == -1)
				break;
			cin >> w;
			tree[x].insert(make_pair(y, w)), tree[y].insert(make_pair(x, w));
		}
	}
	memset(visit, false, V + 1);
	memset(dp, 0, sizeof(dp[0]) * (V + 1));
	bfs(1);
	memset(visit, false, V + 1);
	register int max_pos = max_element(dp, dp + V + 1) - dp;
	memset(dp, 0, sizeof(dp[0]) * (V + 1));
	bfs(max_pos);
	cout << *max_element(dp, dp + V + 1);
	return 0;
}
// *&)*@*

BFS 풀이 방법

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
map<int, set<pair<int, int>>> tree;
bool visit[100001];
int dp[100001];
void dfs(register int n) {
	visit[n] = true;
	for (auto iter = tree[n].begin(); iter != tree[n].end(); ++iter) {
		register int y = iter->first, w = iter->second;
		if (!visit[y])
			visit[y] = true, dp[y] = max(dp[y], dp[n] + w), dfs(y);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int V;
	cin >> V; 
	for (register int v = 0, x, y, w; v < V; ++v) {
		cin >> x;
		while (1) {
			cin >> y;
			if (y == -1)
				break;
			cin >> w;
			tree[x].insert(make_pair(y, w)), tree[y].insert(make_pair(x, w));
		}
	}
	memset(visit, false, V + 1);
	memset(dp, 0, sizeof(dp[0]) * (V + 1));
	dfs(1);
	memset(visit, false, V + 1);
	register int max_pos = max_element(dp, dp + V + 1) - dp;
	memset(dp, 0, sizeof(dp[0]) * (V + 1));
	dfs(max_pos);
	cout << *max_element(dp, dp + V + 1);
	return 0;
}
// *&)*@*

DFS 풀이 방법

 

1번부터 V번까지의 최대 길이를 구하는 방식이 아닙니다.

문제에서 주어진 최대 지름이란 순서와 상관없이 이어진 값이 가장 긴 (최대 지름) 값을 원하는 것입니다.

따라서 1에서 출발했을때 최대로 긴 인덱스를 구하고, 앞서 구한 인덱스부터 시작했을때 최대로 긴 인덱스를 구합니다.

결국 위에서 구한 첫번째 최대 인덱스를 x1, 두번째 최대 인덱스를 x2 라고 할때 x1 ~ x2이 최대 지름이 됩니다.

따라서 bfs 또는 dfs를 2번 진행해주게 됩니다.