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

www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

 

 

알고리즘 종류

    - 트리

    - DFS

 

 

 

사고 과정

    - 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 찾기 위해서 간단한 것부터 생각해보자. 노드 간에 이동거리가 모두 1이라고 해보자.

        * 아래 예시를 보자. 임의의 노드에서 출발하자. 본인은 노드 4를 골랐다. 노드 4에서 출발하여 가장 깊은 곳은 어딜까? 1이다. 그러면 이제 1에서 출발해보자.

        * 노드 1에서 출발해서 가장 깊은 곳은 어딜까? 2와 5이다. 이렇게, 트리의 지름을 구할 수 있다. 그렇다면, 여기에 가중치를 넣어주자. 

 

        * 간선에 가중치를 넣었다. 출제된 문제와 동일하다. 가중치를 더하면서 최고 값과 비교하면 된다. 과정을 위와 동일하다.

 

 

 

구현(C++)

#include <iostream>
#include <cstring>
#include <vector> 
 
using namespace std;
 
int v;
vector<vector<pair<int, int> > > info;
int maxNum = 0;
int start;
 
int isVisited[100001];
 
void dfs(int here, int cost){
    
    if(maxNum < cost){
        maxNum = cost;
        start = here;
    }
    
    for(int i=0; i<info[here].size(); i++){
        int next = info[here][i].first;
        int next_cost = info[here][i].second;
        
        if(isVisited[next]) continue;
        isVisited[next] = 1;
        dfs(next, cost + next_cost);
        isVisited[next] = 0;
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> v;
    info.resize(v+1);
    
    int num, node, cost;
    for(int i=0; i<v; i++){
        cin >> num;
        
        while(true){
            cin >> node;
            if(node == -1) break;
            cin >> cost;
            
            info[num].push_back({node, cost});
        }
    }
    
    isVisited[1] = 1;
    dfs(1, 0);
    
    memset(isVisited, 0, sizeof(isVisited));
    isVisited[start] = 1;
    dfs(start, 0);
    
    cout << maxNum;
}
 
 

 

 

 

시행착오