백준 1967번: 트리의 지름 (C++)

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

1967번: 트리의 지름

---

Solved By: DFS

 

간선의 가중치를 2차원 배열을 선언하여 따로 관리하였는데 이는 메모리 초과가 뜹니다.

 그래서 인접 배열에 pair형으로 향하는 노드와 그에 따른 가중치를 함께 관리하여 DFS를 통해 풀었습니다.

 

제일 긴 지름을 구하려면 leaf node에서부터 시작해야 합니다.

leaf node부터 시작하려면 인접 배열에서 사이즈가 1인 노드부터 DFS를 돌리면 됩니다.

 

#include <iostream>
#include <vector>
#define MAX 10001
#define pii pair<int, int>
using namespace std;

vector<pii> adj[MAX];
bool visited[MAX];
int n;
int maxValue = 0;

void dfs(int now, int c){
    visited[now] = 1;
    maxValue = max(c, maxValue);
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i].first;
        
        if(!visited[next]){
            dfs(next, c + adj[now][i].second);
        }
    }
    
    return;
}

int main(){
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    
    for(int i = 1; i <= n; i++){
        if(adj[i].size() == 1){
            fill(visited, visited + MAX, 0);
            dfs(i, 0);
        }
    }
    
    cout << maxValue;
    return 0;
}