백준 1167번 : 트리의 지름

문제 접근

---

1967 번 코드를 재활용했다. 내가 내 코드를 재활용하는 날이 오다니! 완전 날로 먹는 문제자너? 흠흠.. 아무튼 1967 번과의 차이점은 다음과 같다.

 

1. 입력의 양식이 다르다.

2. 정점의 개수와 가중치 크기 제한이 다르다.

3. 1967 번에서는 단방향 그래프로 트리를 구현했는데, 1167 번은 양방향으로 입력을 한다.

 

1번은 양식에 맞게 바꿔서 해결했고, 2번 또한 크기를 바꿔서 해결했다. 1967 번은 지름이 최대 100 * 10,000 = 1,000,000 으로 int 형에 담을 수 있었고, 1167 번은 안 될 거 같았는데 지름이 최대 10,000 * 10,000 = 1,00,000,000 여서 마찬가지로 int 형에 담을 수 있었다. 3번의 경우, 1967 번의 diameter 함수가 위에서 아래로 흘러간다는 점에 주목해서 위를 부모로 삼아 인자로 전달하는 방식으로 사용할 수 있도록 했다.

 

배운 점!

1. 트리 문제는 정상적인 트리를 입력함을 전제로 한다. tree 가 정상적이지 않다면 Segmentation fault 가 뜨니 트리의 입력을 확인하자.

 

틀리면 바로 잘못된 부분이 보인다.

강해졌군요, AeonFlor.

 

야간 근무서고 왔더니 정신이 이상하다 ㅎㅎ

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, ans=0;
vector<vector<pair<int,int>>> tree(100000);

int diameter(int n, int parent)
{
	// 트리의 leaf 라면 부모 노드와 연결된 간선밖에 없으니, size 가 1 이고, 연결된 노드가 부모라면 return.
	if(tree[n].size() == 1 && tree[n][0].first == parent)
		return 0;
	
	vector<int> inner_max;
	
    // 해당 간선이 부모 노드와 연결되지 않을 때만 탐색.
	for(int i=0; i<tree[n].size(); ++i)
		if(tree[n][i].first != parent)
			inner_max.push_back(tree[n][i].second + diameter(tree[n][i].first, n));
	
	sort(inner_max.begin(), inner_max.end());
	
	if(tree[n].size()>1)
		ans = max(ans, inner_max[inner_max.size()-2]+inner_max[inner_max.size()-1]);
	
	return inner_max[inner_max.size()-1];
}

int main(void)
{
	int s, e, weight;
	
	cin>>n;
	
	while(n--)
	{
		cin>>s;
        
        // 깔끔한 코드를 위해 입력받으면서 바로 조건 확인.
		while(cin>>e && e!=-1)
		{
			cin>>weight;
			tree[s].push_back(make_pair(e,weight));
			//cout<<"[PUSH SUCCESS] "<<child<<" : "<<weight<<'\n';
		}
	}
	
	ans = max(diameter(1,0), ans);
	
	cout<<ans<<'\n';
}