[백준 C++] 1967 트리의 지름 - 깊이우선탐색

1967번: 트리의 지름

#include <iostream>
#include <list>
using namespace std;

int Max = 0, A = 1, B = 1;
list<pair<int, int>> Neighbors[10001];
bool Visited[10001];

void DFS(bool bACheck, int Current, int Length)
{
	Visited[Current] = true;

	int Cnt = 0;
	for (const pair<int, int>& N : Neighbors[Current])
	{
		int Neighbor = N.first;
		int Weight = N.second;

		if (!Visited[Neighbor])
		{
			DFS(bACheck, Neighbor, Length + Weight);
			++Cnt;
		}
	}

	if (Cnt == 0 && Length > Max)
	{
		Max = Length;
		if (bACheck)
		{
			A = Current;
		}
		else
		{
			B = Current;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N;
	cin >> N;
	for (int i = 0; i < N - 1; ++i)
	{
		int P, C, W;
		cin >> P >> C >> W;
		Neighbors[P].emplace_back(C, W);
		Neighbors[C].emplace_back(P, W);
	}

	DFS(true, 1, 0);

	Max = 0;
	for (int i = 1; i <= N; ++i)
	{
		Visited[i] = false;
	}

	DFS(false, A, 0);

	cout << Max;
}

---

 

깊이 우선 탐색으로 푸는 트리 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 인접 리스트, 방문 배열 초기화 - 부모, 자식 노드 모두 양방향으로 정보 저장

2. 1번 노드로부터 가장 멀리 떨어져있는 A 노드 탐색 - DFS

3. A 노드로부터 가장 멀리 떨어져있는 B 노드 탐색 - DFS

4. A ~ B 사이의 길이 출력