[DFS]백준1967번 트리의 지름

백준 1967

백준 1967번

트리의 지름

처음에 문제를 너무 복잡하게 생각해서 도저히 해결 방법을 찾을 수가 없었다.

그래서 여기저기 참고한 결과는 다음과 같다.

1. 임의의 한 노드에서 가장 거리가 먼 노드를 찾는다.
2. 찾은 노드로부터 가장 거리가 먼 노드를 찾는다.
3. 두 노드 사이의 거리가 트리의 지름(모든 경로들 중에서 가장 긴 것의 길이)이 된다.

두 노드 사이의 거리가 가장 긴 노드를 찾으려면, 그리고 문제에서 제시하는 조건을 모두 만족하려면

임의의 한 노드(라고 하는데 나는 루트 노드로 이해했다.)로부터 가장 거리가 긴 노드를 찾아야 한다. 가장 거리가 긴 노드를 찾으면 우선 한 쪽을 완성할 수 있다.

루트 노드로부터 제일 먼 노드 ‘9’ . 이 때 한 쪽이 완성된다.

‘9’에서부터 제일 먼 노드를 찾는다.

‘12’가 9로부터 가장 멀리 떨어져있다. 이 때 오른쪽이 완성된다.

왼쪽도 가장 크고, 오른쪽도 가장 크다.

루트 노드로부터 가장 거리가 먼 노드와 루트 노드로부터 가장 거리가 가장 거리가 먼 노드를 찾고, 해당 노드로부터 다시 거리가 가장 먼 노드를 찾고 두 노드 사이의 거리를 구하면 된다.

풀이를 안봤으면 혼자 생각해내기는 어려웠을 것 같다.

구현에서 가장 중요했던 것은 노드들의 가중치를 관리하는 부분이었다.

나는 dfs를 사용했는데, 노드를 방문했을 때 stack에 가중치를 넣고 변수에 더한 다음, 다음 dfs를 호출하고 stack.top과 pop 을 이용해 방금 전 더했던 값을 다시 돌려준다.

이 방법대로면 가중치를 가진 그래프를 전부 탐색할 수 있다.

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

vector<pair<int,int> > nodes[10001];
bool visited[10001] = {false,};

int dfs(int n,int sum);
stack<int> s;
int maxWeight = 0;
stack<int> maxNodes;

int main(){
    int N;
    cin >> N;
    for(int i=0;i<N-1;i++){
        int parent, child, weight;
        cin >> parent >> child >> weight;
        nodes[parent].push_back(make_pair(child,weight));
        nodes[child].push_back(make_pair(parent,weight));
    }

    visited[1] = true;
    dfs(1,0);
    int pos = maxNodes.top();
    maxNodes.pop();
    while(!s.empty()){
        s.pop();
    }
    memset(visited,false,sizeof(visited)); 
    maxWeight = 0;
    dfs(pos,0);
    cout << maxWeight << endl;
    // cout << maxNodes.top() << endl;
}

int dfs(int n, int sum){
    // cout << n << ", sum is " << sum << endl;
    visited[n] = true;
    int weight = sum;
    for(int i=0;i<nodes[n].size();i++){
        if(!visited[nodes[n][i].first]){
            s.push(nodes[n][i].second);
            weight += nodes[n][i].second;
            weight = dfs(nodes[n][i].first,weight);
        }
    }
    if(weight >= maxWeight){
        if(!maxNodes.empty()){
            maxNodes.pop();
        }    
        maxWeight = weight;
        maxNodes.push(n);
    }
    if(!s.empty()){
    // cout << s.top() << endl;
    weight -= s.top();
    s.pop();
    }
    return weight; 
}