[백준] 알고리즘 1967번 - 트리의 지름 문제

트리의 지름 문제

소스 코드

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[10001];
bool check[10001];
int weight[10001];
void dfs(int x) {
	check[x] = true;
	int size = v[x].size();
	for (int i = 0; i < size; i++) {
		if (check[v[x][i].first] == false) {
			weight[v[x][i].first] = weight[x] + v[x][i].second;
			dfs(v[x][i].first);
		}
	}
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int n;
   cin >> n;
   for (int i = 1; i < n; i++) {
	   int x, y, z;
	   cin >> x >> y >> z;
	   v[x].push_back({ y,z });
	   v[y].push_back({ x,z });
   }
   dfs(1);
   
   int idx=0,Max = 0;
   for (int i = 1; i <= n; i++) {
	   if (weight[i] > Max) {
		   Max = weight[i];
		   idx = i;
	   }
   }
   for (int i = 1; i <= n; i++) {
	   weight[i] = 0;
	   check[i] = false;
   }
   dfs(idx);
   Max = weight[1];
   for (int i = 1; i <= n; i++) {
	   if (weight[i] > Max) {
		   Max = weight[i];
	   }
   }
   cout << Max;
}

해결방법

이건 솔직히 이 문제만의 해결 방법을 알지못하면 해결하기 어렵다고 볼 수 있습니다.

먼저 해결 방법을 말해드리자면, dfs를 2번 이용하여 문제를 해결해야 한다는 것입니다.

또한 트리의 특성상 한번 정점을 방문하여 bfs, dfs를 하게되면 모든 정점을 다 방문하게 된다는 특징을 이용합니다.

dfs로 각 정점들의 깊숙히 들어가 가중치들의 합들을 weight 배열에 저장하여 가장 큰 값의 인덱스를 찾습니다.

찾은 인덱스 값을 이용하여 다시한번 dfs를 돌리면 그게 바로 이문제의 정답을 출력하는 것입니다.

 

저도 사실 왜 이게 정답이 되는지 이유는 잘모르겠고, 다른분들의 의견들을 참고하여 문제를 해결하였습니다.

이후 업데이트를 통해 왜 이렇게 해야만 문제를 해결할 수 있는지 업데이트 하도록 하겠습니다.