문제 요약
트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 구하시오. (단, 루트 노드는 1이다.)
아이디어
한 노드에서 자식 노드까지의 거리 가장 큰 2개를 더하여 그 최댓값을 구한다.
풀이과정
이러한 형태의 트리가 있을 때 트리의 깊이를 알 수 있다.
깊이가 가장 깊은 것 부터 연산하여 자신의 부모 노드에 간선의 가중치+max(D[그 노드의 번호]) 를 기억한다.
D[6]=D[7]+15, D[6]=D[8]+4, D[6]=D[9]+9 로
D[6]에는 {15, 9, 4, 0}이 기억되어 있다. (0은 초기값)
이러한 연산을 계속한다면
D의 값은 이러할 것이다.
그러면 K에 D안에 값들의 최대값 2개를 더하는 연산을 한다.(K초기값 : -1)
K=max(K, D[1][0]+D[1][1]) --> K=24 (D[1][0]=19, D[1][1]=5)
K=max(K, D[2][0]+D[2][1]) --> K=24 (D[2][0]=3, D[2][1]=1)
K=max(K, D[3][0]+D[3][1]) --> K=24 (D[2][0]=18, D[2][1]=0)
...
K=max(K, D[6][0]+D[6][1]) --> K=24 (D[2][0]=15, D[2][1]=9)
...
K=max(K, D[9][0]) --> K=24 (D[9][0]=0)
으로 트리의 지름은 K=24가 된다.
코드 (C++)
#include <bits/stdc++.h>
using namespace std;
int c2[10010], c3[10010];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin>>n;
vector<int> A[10010];
for(int i=1; i<n; i++)
{
int a, b, c; cin>>a>>b>>c;
A[a].push_back(b);
c3[b]=a; c2[b]=c;
}
priority_queue<pair<int, int> > B;
priority_queue<int> D[10010];
queue<int> a; a.push(1);
B.push({0, 1}); D[1].push(0);
while(!a.empty())
{
int b=a.front(), P=B.top().first;
a.pop(); D[b].push(0);
for(int i=0; i<A[b].size(); i++)
{
a.push(A[b][i]);
B.push({P+1, A[b][i]});
}
}
while(!B.empty())
{
int b2, d;
b2=B.top().second;
d=D[b2].top()+c2[b2]; B.pop();
D[c3[b2]].push(d);
}
int k=0;
for(int i=1; i<=n; i++)
{
int p=0;
for(int j=0; j<2 && !D[i].empty(); j++)
{
p+=D[i].top(); D[i].pop();
}
if(i==1) k=p;
k=max(k, p);
}
cout<<k;
return 0;
}
'코딩 > PS' 카테고리의 다른 글
[백준 1520] 내리막 길 / C++ (0) | 2022.11.26 |
---|---|
[백준 1110] 더하기 사이클 / 증명 (0) | 2022.09.06 |
[NYPC 2022년도] 카트라이더 보드게임 / 2번 문제 (0) | 2022.08.25 |
[NYPC 2022년도] 인류의 적 모기 퇴치 / 1번 문제 (0) | 2022.08.25 |
[백준 1050] 물약 (0) | 2022.08.17 |