[백준] 1167- 트리의 지름(C++)

문제링크: www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

트리에서 가장 긴구간을 구하기 위해서는 

 

• 1. 한점에서 가장 먼 점을 찾는다.
• 2. 해당 점에서 가장 멀리 갈 수 있는 거리를 구한다.

두가지를 순서대로 구현해주면 됩니다.

저는 이전에 유사한 문제를 풀어봐서 쉽게 풀었네요.

 

 

 

 

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int v = 0;
vector <pair<int, int>> vec[100001];
int far = 0, far_val = 0;
bool visited[100001];


void dfs(int current, int sum) {
	if (sum > far_val) {
		far = current;
		far_val = sum;
	}

	for (int i = 0; i < vec[current].size(); i++) {
		int num = vec[current][i].first;
		if (visited[num] == 0) {
			visited[num] = 1;
			dfs(num, sum + vec[current][i].second);
		}
	}


}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	//input
	cin >> v;
	for (int i = 1; i <= v; i++) { // 간선 개수만큼 반복
		int a = 0;
		cin >> a;
		int b = 0, bval = 0;
		while (1) {
			cin >> b;
			if (b == -1)
				break;
			cin >> bval;
			vec[a].push_back(make_pair(b, bval));
			vec[b].push_back(make_pair(a, bval));

		}
	}

	//1. 가장 먼 곳 찾기
	memset(visited, 0, sizeof(visited));
	visited[1] = 1;
	dfs(1, 0);
	//cout << "far " << far << endl;
	
	//2. 결과 도출하기
	int f = far;
	far = 0, far_val = 0;
	memset(visited, 0, sizeof(visited));
	visited[f] = 1;
	dfs(f, 0);

	cout << far_val << endl;
	return 0;
}