[백준 1167] 트리의 지름 (c++)

문제풀이

매우 아이디어가 좋은 문제이다.

 

루트 노트로부터 가장 멀리있는 노드로부터

또다시 가장 먼노드를 찾으면 그 두 노드가 지름을 담당하는 두노드다 그 두노드의 사이의 길이가 트리의 지름의 길이이다.

소스코드

 

#include <iostream>
#include <vector>
using namespace std;
 
typedef struct treeNode{
    int edge,num;
    treeNode(){}
    treeNode(int e, int n){
        edge = e; num = n;
    }
}treeNode;
 
int numNode;
vector<vector<treeNode>> graph;
 
int max_distance_node=0;
int max_distance=0;
 
void dfs(int node, int edgeLength,vector<bool> visited){
    if(max_distance<edgeLength){
        max_distance = edgeLength;
        max_distance_node = node;
    }
    for(int i=0;i<graph[node].size();i++){
        int next_node = graph[node][i].num;
        if(!visited[next_node]){
            visited[next_node] = true;
            dfs(next_node, edgeLength + graph[node][i].edge,visited);
        }
    }
}
 
int main() {
    vector<bool> visited;
    cin>>numNode;
    graph.assign(numNode+1,vector<treeNode>(0,treeNode(0,0)));
    visited.assign(numNode+1, false);
    
    for(int i=0;i<numNode;i++){
        int node;
        cin>>node;
        while(1){
            int inputNode;
            cin>>inputNode;
            if(inputNode ==-1)
                break;
            int edge;
            cin>>edge;
            graph[node].push_back(treeNode(edge,inputNode));
        }
    }
    
    visited[1] = true;
    dfs(1,0,visited);
    visited[1] = false;
    
    int start = max_distance_node;
    max_distance_node = 0;
    
    
    visited[start] = true;
    dfs(start ,0, visited);
    visited[start] = false;
    
    cout<<max_distance<<endl;
    
    return 0;
}
 

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

1167번: 트리의 지름