[백준 BOJ][C++]1967번 트리의 지름 풀이: DFS

 

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

1967번: 트리의 지름

 

 

 

 이 문제는 DFS를 이용하여 해결할 수 있습니다. 

 

 tree[n] 은 노드 n의 연결된 노드와 그 가중치의 쌍을 저장한 벡터입니다. 

 

 어느 노드이든지간에 dfs()를 실행하여 가장 멀리 떨어진 리프 노드를 찾으면 그 노드는 트리의 지름의 양 끝 점 중, 한 점이 됩니다.

 

 때문에 dfs를 호출한 노드로부터 가장 멀리 떨어진 리프 노드를 찾도록 dfs를 구현합니다. 

 

 

 dfs(n, 0) 을 실행하면 노드 n으로부터 시작하여 leaf node를 만날 때마다, temp_sum과 point를 갱신하여 n으로부터 가장 멀리 떨어진 노드와 그 거리를 temp_sum과 point에 저장합니다. 

 

 처음 dfs(1, 0)을 실행하면 1번 노드로부터 가장 멀리 떨어진 노드가 point에 저장되고, 그 거리는 temp_sum에 저장됩니다. 

 

 이후 temp_sum을 0으로 초기화 한 뒤, dfs(point, 0)을 실행해주면 temp_sum에 트리의 지름이 저장됩니다. 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

#define MAX 10001

int n;
vector<pair<int, int>> tree[MAX];
bool visit[MAX] = { false, };
int temp_sum, point;

void dfs(int u, int sum) {

	bool flag = false;

	for (int i = 0; i < tree[u].size(); i++) {
		int next = tree[u][i].first;
		if (!visit[next]) {
			if (!flag)
				flag = true;

			visit[next] = true;
			dfs(next, sum + tree[u][i].second);
		}
	}

	if (!flag) { //leaf node일 때
		if (sum > temp_sum) {
			temp_sum = sum;
			point = u;
		}
		return;
	}
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;

		tree[u].push_back({ v, w });
		tree[v].push_back({ u, w });
	}

	visit[1] = true;
	dfs(1, 0);

	memset(visit, false, sizeof(visit));
	temp_sum = 0;

	visit[point] = true;
	dfs(point, 0);

	cout << temp_sum;

	return 0;
}