1967. 트리의 지름

문제링크 : https://www.acmicpc.net/problem/1967

<입력>

노드의 개수 n

(n-1)개의 간선 정보 (부모, 자식, 가중치)

<출력>

트리의 지름(트리의 두 정점 간의 거리 중 가장 최대값)

<풀이>

우선, 트리의 가중치가 음수 혹은 0인 경우가 존재하지 않는다면 두 정점간의 거리의 최대값은 리프 - 리프 노드 사이에 존재한다.

이 생각을 시작으로 문제를 접근했다.

루트 노드의 번호는 언제나 1이다.

이 문제는 부분으로 나눌 수 있다.

6번 노드가 루트인 서브 트리의 최대값은 (10+6=16)이고 5번 노드가 루트인 서브 트리의 최대값은 (15+4=19)이다.

그리고 각각 위로 갈 수 있는 최대 경로인 10과 15를 넘겨준다.

다음으로 3번 노드가 루트인 서브트리의 최대값은 5번 노드로부터 받은 (15+11=26), 6번 노드로부터 받은 (10+9=19)의 합인 (26+19=45)가 된다.

그렇게 각 노드의 서브트리의 최대값을 저장하면서 최종 루트인 1에 도달할 때까지 연산을 수행한 다음 가장 큰 값을 찾는다면 해결할 수 있다.

위 트리를 예시로 진행한다면 아래 그림과 같다.

---

- 소스 코드 -

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
typedef struct Edge{
    int parent; // 부모 노드
    int parent_weight; // 부모와 자신간의 간선의 가중치
    int cur_maximum; // 위로 넘겨주는 값이 아닌 현재 노드에서의 최대값
    int index; // 현재 노드의 인덱스 번호(curNode 값 갱신하기 위함)
    vector<int> son; // 자식 배열
    Edge(){
        parent=0;
        parent_weight=0;
        cur_maximum=0;
        index=0;
    }
}E;
 
E edges[10002]; // 엣지를 저장합니다.
int maximum[10002]; // 노드별 최대값을 저장하기 위한 배열
 
int solve(E curEdge){ // bfs
    if(curEdge.son.empty()){ // 리프노드일 경우 부모와의 간선 가중치를 리턴
        return curEdge.parent_weight;
    }
    int maximum1=0; // 최대값 1번(제일 큰)
    int maximum2=0; // 최대값 2번(2번째로 큰)
 
    for(auto it:curEdge.son){
        int temp=solve(edges[it]);
        if(temp>maximum1){
            maximum2=maximum1;
            maximum1=temp;
        }else if(temp==maximum1){
            maximum2=temp;
        }else if(temp>maximum2){
            maximum2=temp;
        }
        // 모든 자식 노드에 대해 경로의 최대값을 구한다.
        // 자식 노드가 1개일 경우 나머지는 0으로 초기화되므로 걱정 X
    }
    
    maximum[curEdge.index]=maximum1+maximum2;
    // 현재 노드가 루트인 서브트리의 지름
    return maximum1+curEdge.parent_weight;
    // 최대값과 부모와의 거리를 더해서 부모에게 리턴
}
int main(void){
    int n;
    scanf("%d",&n);
    // 입력 받기
    for(int i=1;i<n;i++){
        int p,s,w;
        scanf("%d %d %d",&p,&s,&w);
        edges[p].son.push_back(s);
        edges[s].parent=p;
        edges[s].parent_weight=w;
        edges[s].index=s;
    }
    // solve 함수를 이용해 bfs를 수행하며 최대값 배열 채우기
    int result=0;
    result=solve(edges[1]);
 
    // 최대값 배열에서 최대값 찾기
    // 루트에서 최대일 경우 0번 인덱스에 값이 채워지므로 0번부터 확인
    for(int i=0;i<=n;i++){
        result=max(maximum[i],result);
    }
 
    printf("%d\n",result);
}

---