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

1167번: 트리의 지름

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

int N;
list<pair<int, int>> Neighbor[100000];
bool Visited[100000];

int Max;
int A, B;
void DFS(bool bFindA, int Idx, int Length)
{
	Visited[Idx] = true;

	int Cnt = 0;
	for (const pair<int, int>& N : Neighbor[Idx])
	{
		if (!Visited[N.first])
		{
			DFS(bFindA, N.first, Length + N.second);
			++Cnt;
		}
	}

	if (Cnt == 0)
	{
		if (Length > Max)
		{
			Max = Length;

			if (bFindA)
			{
				A = Idx;
			}
			else
			{
				B = Idx;
			}
		}
	}
}

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

	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int Src;
		cin >> Src;
		while (true)
		{
			int Dst;
			cin >> Dst;
			if (Dst == -1)
			{
				break;
			}

			int Cst;
			cin >> Cst;
			Neighbor[Src - 1].emplace_back(Dst - 1, Cst);
		}
	}

	DFS(true, 0, 0);
	memset(Visited, false, sizeof(Visited));
	DFS(false, A, 0);

	cout << Max;
}

---

 

깊이 우선 탐색을 두 번 이용해서 트리의 지름을 구하는 문제입니다.

최종적으로 트리의 지름을 이루는 두 노드를 찾아서 그 길이를 구하면 됩니다.

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

 

1. 인접노드 리스트 구성

2. 아무노드로부터 출발해서 출발 노드로부터 가장 거리가 먼 노드 A 탐색 후 저장 - DFS 이용

3. 2번에서 찾은 노드 A로부터 출발해서 가장 거리가 먼 노드 B 탐색 - DFS 이용

4. 위에서 찾은 노드 A와 노드 B 사이의 거리가 트리의 지름