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

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

 

 

알고리즘 종류

    - 트리

    - DFS

 

 

 

사고 과정

    - 가장 긴 한 쪽 노드에서 다른 쪽 가장 긴 노드로 이동해야 한다. 그러기 위해서는 양방향으로 움직일 수 있어야 한다. 

    - DFS로 root에서 가장 긴 한 쪽 노드를 찾으면, 그곳을 start 노드로 잡고 그곳에서 다시 DFS를 하여, 가장 긴 다른 한 쪽 노드를 찾는다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int n;
int answer = 0;
int deepestNode;
int isVisited[10001];
 
vector<vector< pair<int, int> > >  g;
 
 
void dfs(int s, int sum){
    
    isVisited[s] = 1;
    
    if(sum > answer){
        answer = sum;
        deepestNode = s;
    }
    
    for(int i=0; i<g[s].size(); i++){
        if(isVisited[g[s][i].first]) continue;
        
        isVisited[g[s][i].first] = 1;
        dfs(g[s][i].first, sum + g[s][i].second);
        isVisited[g[s][i].first] = 0;
    }
}
 
int main(void){
    
    scanf("%d", &n);
    g.resize(n+1);
    
    int p, c, cost;
    for(int i=0; i<n-1; i++){
        
        scanf("%d %d %d", &p, &c, &cost);
        g[p].push_back({c, cost});
        g[c].push_back({p, cost});
    }
    
    memset(isVisited, 0, sizeof(isVisited));
    dfs(1, 0);
    memset(isVisited, 0, sizeof(isVisited));
    dfs(deepestNode, 0);
    
    cout << answer;
}

 

 

 

시행착오