C++ [백준]1967번 트리의 지름

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

1967번: 트리의 지름

 

솔루션

---

트리의 자식이 2개가 아니라 여려개가 될 수도 있어서, 벡터를 이용해 간선과, 가중치를 담았고,

 

각 간선을 타고 내려갔을 때의 최대의 지름 길이를 리턴을 해 주었다.

 

(리턴을 할 때, 간선 중 하나만 리턴을 해야 하므로 가장 큰 가중치를 갖는 간선 한개만을 택해서 리턴을 했다)

그리고 각 간선들의 가중치 연산이 끝나면, 가장 큰 노드 2개를 선택해서 길이를 더해서 최대값과 비교를 했다.

 

 

 

코드

---

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

int N;
int cnt;
vector<pair<int, int>> v[10002];

int findMax(int node) {
	//가장 큰 가중치를 담을 temp1 변수
    int temp1 = 0;
    //두번째로 큰 가중치를 담을 temp2 변수
	int temp2 = 0;
	
	for (int i = 0; i < v[node].size(); i++) {
    	//각 간선의 최대 가중치+ 연결되어있는 가중치
		int cal = findMax(v[node][i].first) + v[node][i].second;
		if (temp1 < cal) {
        	//간선의 가중치 최대값을 초기화 해 주고,
			temp2 = temp1;
			temp1 = cal;
		}
		else if (temp2 < cal) {
        	//만약 cal이 가장 크지 않지만, 2번째로 클 수도 있기에,
			temp2 = cal;
		}
	}
	if (cnt < temp1 + temp2) {
    	//각 부분 노드들의 각각 가중치를 더했을 때와 비교
		cnt = temp1 + temp2;
	}
    //한 간선만 리턴을 해 줘야 함.
	return temp1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int str, dest, cost;
		cin >> str >> dest >> cost;
		v[str].push_back({ dest,cost });
	}

	findMax(1);

	cout << cnt << "\n";
}