[백준 1967] - 트리의 지름(C++)[골드4]

📕문제

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

1967번: 트리의 지름

---

🔎문제 설명

트리의 지름을 구하는 문제입니다.
여기서 트리의 지름이란 가장 먼 거리의 노드를 쫙 늘려서 원형태로 만들면 가장 먼 노드 2개가 양 끝점으로 지름을 이루는 형태가 될 것입니다.

해당 그림에서는 9와 12를 꼭짓점으로 쫙 늘리면 그 경로의 길이가 트리의 지름이 될 것입니다.

이렇게 우리는 각 노드들 사이의 경로의 길이를 구해서, 그 길이가 최댓값이 되는 경우를 구해주면 됩니다.

 

우선 각 노드들의 가중치는 음수가 아닙니다. 양의 정수라고 명시되어있기 때문에 1번에서 가장 먼 지점까지의 노드가 꼭짓점의 한 부분이 될 것입니다.

그 지점까지의 거리가 최댓값이기 때문에, 그 노드를 포함하는 경로가 당연히 트리의 지름이 될 것입니다.

 

루트에서 가장 먼 노드는 그림에서 9번이 될 것입니다.

이제 다음에는 9번에서 가장 먼 노드를 구하면 그 경로의 길이가 트리의 지름이 될 것입니다.

 

9번에서 가장 먼 노드는 12입니다. 따라서 트리의 지름은 15+11+9+10인 45가 되는 것입니다.

 

따라서 우리는 각 노드별로 갈 수 있는 경로를 인접리스트로 구한 뒤, 인접리스트에는 도착지점과 그 가중치를 저장해 줍니다.

기본적인 탐색은 DFS를 사용해서, 가장 먼 노드의 길이와 가장 먼 노드를 구해줬습니다.

---

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int>V;
vector<pair<int,int> >node[10001];
int maxVal=-1, maxnode=0;
void dfs(int now, int val);
int main(){
    cin>>n; //정점의 개수
    V.resize(n+1,0);
    int s,e,w;
    for(int i=0; i<n-1; i++){
        cin>>s>>e>>w; //출발,도착,가중치
        node[s].push_back(make_pair(e,w));
        node[e].push_back(make_pair(s,w));
    }
    dfs(1,0); //루트에서 가장 먼 노드를 찾음.
    V.assign(n+1,0);
    maxVal=-1;
    dfs(maxnode,0);
    cout<<maxVal<<endl;
}
void dfs(int now, int val){

    V[now]=1; //방문 처리
    if(maxVal < val){ //최대값이 갱신될 경우
        maxVal=val;
        maxnode=now;
    }
    for(int i=0; i<node[now].size();i++){ //현재 지점에서 갈 수 있는 노드.
        if(V[node[now][i].first]==1) //이미 방문한 경우
            continue;
        dfs(node[now][i].first,val+node[now][i].second);
    }
}

 

😀느낀 점

• 다른 방법으로 풀고 싶었는데.. 딱히 떠오르는 방법이 없네요
• 만약 가중치가 음수였다면, 이 방법으로는 못 풀 것입니다.
• 인접행렬보다는 인접리스트를 사용합시다!