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

1167번: 트리의 지름

cpp

#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 사이의 거리가 트리의 지름