BOJ 1967 - 트리의 지름

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

제목이 곧 내용인 문제

 

<문제설명>

트리의 지름을 구하라

 

<풀이 1>

https://suuntree.tistory.com/171아이디어에 대한 추가설명

 

임의의 점에서 제일 먼 점 u와 u에서 제일 먼 점 v사이의 길이를 구하면 된다.

 

어떤 점에서 제일 긴 곳까지의 길이는 어떻게 구할까? 가중치가 없는 트리에선 dfs의 깊이가 곧 길이가 된다. 이 문제는 가중치가 있는 그래프이므로 1대신 w 더해주면 된다. 모든 정점에서 이 길이의 최대를 찾으면 된다.

 

dfs 깊이를 효과적으로 유지하려면 함수에 깊이를 의미하는 파라미터를 추가해주면 된다.

 

dfs(u, prv, d)꼴로 한 번의 dfs로 가장 먼 점과 그때의 거리를 구할 수 있다.

 

<코드>

int n, dst, st;
vector<P> adj[MAX];
void dfs(int u, int p, int d) {
	//정점을 방문할 때 마다 깊이(거리) 갱신해주고 거리가 가장 멀 때 점을 st에 저장한다
	if (dst < d) {
		dst = d;
		st = u;
	}
	for (P pp : adj[u]) {
		int v = pp.first, w = pp.second;
		if (v != p) dfs(v, u, d + w);
	}
}

int main() {
	FAST;
	cin >> n;
	for (int i = 0, u, v, w; i < n - 1; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
	}
	dst = 0; dfs(1, 0, 0);
	dst = 0; dfs(st, 0, 0);
	cout << dst << '\n';
}

 

<풀이2>

https://blog.encrypted.gg/116이 블로그에서 설명해주신 방법을 리뷰

 

부모->자식 간선만 이어주고 트리의 재귀적인 성질을 이용해서 dp.

정점당 자식이 둘 이상이라고 잠시 가정.

d[u] : 루트가 u인 서브트리에서 u와 가장 먼 지점까지의 거리라고 하면 다음과 같은 점화식 성립.

 최대 지름이 될 가능성이 있는 것은 d[u]의 후보 중 최대값(fi)과, 두번째로 큰 값(se)의 합이다.

 

1. d[u]=0 초기화 ( d[i]>=0이므로 맨 처음에 -1로 초기화해두고 방문처리 역할도 함)

2. 방문한적 없는 모든 자식 정점v에 대해 최대 지름 갱신, d[v] 초기화. (dfs(v) : 재귀)

3. 초기화된 d[v]값으로 d[u]의 최대값 갱신. fi, se값 갱신

4. 모든 정점에 대해 처리 후 최대 지름을 fi+se를 이용하여 갱신

 

한쪽으로 치우친 트리(자식 수 하나 이하)인 경우 d[u]가 트리의 지름이 될 수 있으므로 마지막에 모든 d에 대해 최대 지름 갱신해주면 된다.

 

<코드>

typedef pair<int, int> P;
const int MAX = 1e4 + 2;

int n, d[MAX], diameter; //i가 루트인 서브트리에서 i와 가장 먼 점까지의 거리
vector<P> child[MAX];
void dfs(int u) {
	d[u] = 0;
	int fi = -1, se = -1;
	for (P pp : child[u]) {
		int v = pp.first, w = pp.second;
		if (d[v] == -1) dfs(v);
		int temp = d[v] + w;
		d[u] = max(d[u], temp);
		if (fi < temp) {
			se = fi;
			fi = temp;
		}
		else if (se < temp)
			se = temp;

	}
	if(se!=-1)
		diameter = max(diameter, fi + se);
}

int main() {
	FAST;
	memset(d, -1, sizeof(d));
	cin >> n;
	for (int i = 0, u, v, w; i < n - 1; i++) {
		cin >> u >> v >> w;
		child[u].push_back({ v,w });
	}
	
	dfs(1);
	for (int i = 1; i <= n; i++)
		diameter = max(diameter, d[i]);

	cout << diameter << '\n';
}

 

<생각>

루트가 항상 1임을 이용함.

 

d값은 참조투명하고 현재 정점에 대해 인접 정점들로 점화식이 세워진다->dp

u에서 가장 먼 거리인 fi와 두번째로 먼 거리 se를 자연스럽게 유지하는 것 유념