BOJ 1167 트리의 지름

이 문제는 이전에 풀었던 문제와 입력 방식만 다른 완전히 같은 문제이다. https://devconf.tistory.com/40

BOJ 1967 트리의 지름

기본적인 방식은 특정 아무 위치에서 DFS를 통해 길이가 최대가 되는 시작점을 구하고, 그 시작점에서 다시한번 DFS를 돌리면 된다.

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

int v;
vector<pair<int, int>> adj[100001];
bool visited[100001];
int startIdx = 0;
int maxWeight = 0;

void dfs(int idx, int sumWeight)
{
	if(visited[idx] == true)
	{
		return;
		
	}

	visited[idx] = true;

	for(int i = 0; i < adj[idx].size(); i++)
	{
		pair<int, int> front = adj[idx][i];
		int nextNode = front.first;
		int weight = front.second;

		if(maxWeight <= sumWeight + weight && visited[nextNode] == false)
		{
			startIdx = nextNode;
			maxWeight = sumWeight + weight;
		}
		dfs(nextNode, sumWeight + weight);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	memset(visited, false, sizeof(visited));

	cin >> v;

	for(int i = 1; i <= v; i++)
	{
		int end = 0;
		int vIdx = 0;
		cin >> vIdx;

		int cnt = 0;
		int node, w;
		while(end != -1)
		{
			cnt++;
			cin >> end;
			if(cnt % 2 == 1)//연결된 노드
			{
				node = end;
			}
			else
			{
				w = end;
				adj[vIdx].push_back({ node,w });
			}
		}
	}

	dfs(1,0);

	maxWeight = 0;
	memset(visited, false, sizeof(visited));

	dfs(startIdx,0);

	cout << maxWeight;
}