[백준] 1967번 : 트리의 지름 [C/C++]

#문제

1967번: 트리의 지름

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

---

#접근방법

트리의 정보를 단방향 노드로 배열에 저장해준다음, 루트부터 아래로 내려가면서 bfs를 이용하여 트리의 지름을 구해주면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int> > tree[10005];

int ans;

int dfs(int x){
    int biglen=0;
    int len1=0;
    int len2=0;
    int k;

    for(int i=0;i<tree[x].size();i++){
        k = dfs(tree[x][i].first)+tree[x][i].second;
        if(k>len1 || k>len2){
            len2 = len1;
            len1 = k;
        }
        biglen = max(biglen,k);
    }

    ans = max(ans,len1+len2);

    return biglen;
}

int main(){
    int n,a,b,w;

    scanf("%d",&n);

    for(int i=0;i<n-1;i++){
        scanf("%d %d %d",&a,&b,&w);
        tree[a].push_back(make_pair(b,w));
    }

    dfs(1);

    printf("%d\n",ans);

    return 0;
}

 

트리의 정보는 부모노드, 자식노드, 가중치로 입력를 받는다.

 

tree라는 pair로 이루어진 벡터배열에 트리의 정보를 저장해준다.

 

루트는 1이라고 문제에 나와있으므로 dfs(1)을 호출하여 트리의 지름을 구해준다.

 

현재 노드에 있는 자식들의 사이즈만큼 반복문을 돌리면서 k값을 구해준다.

k는 자식의 가중치와 자식 밑에있는 가장 긴 길이의 합이다.

가장 큰 k값을 biglen에 저장시켜주고,  조건문을 통해 가장 큰 k값과 두 번째로 큰 k값을 구하여 len1과 len2에 저장시켜준다.

 

len1과 len2의 합이 현재 노드를 기준으로 가장 큰 트리의 지름이된다. 이 값을 ans에 저장시켜준다.

 

return biglen;으로 가장 큰 길이를 리턴시켜준다. 이것을 루트에서 아래로 반복하면 모든 노드를 기준으로 가장 큰 트리의 지름을 구할 수 있으므로 ans를 출력하면 정답이다.

---

#성능

---

#정리

트리의 자식이 여러개인 경우와 편향트리인 경우를 생각하여 코드를 잘 작성할 것,

 

dfs로 트리의 지름을 구할 수 있는 구현력을 갖추고 있으면 풀 수 있는 문제였다.