문제 1167. 트리의 지름(에센셜 4)

문제 링크

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

 

난이도 : 골드 2

 

문제 요약 설명

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

1번째 줄 : 정점의 개수 V

이 후 각각의 V개의 줄:

• 정점 번호가 먼저 주어진다.
• 연결된 정점의 번호와 거리가 주어진다.(반복적으로 주어질 수 있다.)
• 마지막에 -1이 입력으로 주어진다.

입력 제한

정점의 개수 V (2 ≤ V ≤ 100,000)

0 < 정점 사이의 거리 <= 10,000

입력 예제

// input
5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

// ans
11

 

풀이 방식

• 1967번 문제와 동일한 문제. 단, 모든 간선은 2번씩 나타난다.(A와 B사이의 간선 1개(가중치 w)로 예를 들자면, A에서는 B w, B에서는 A w로 나타난다.) 그렇기 때문에 자식, 부모 노드의 관계를 입력에서 알기 어렵다. 
• 기본적인 알고리즘은 똑같지만 방문여부를 확인할 필요가 있다. 그래서 추가적으로 방문 여부를 확인하는 visited배열을 추가한다. 그 외에는 전부 1967번과 동일하다. 알고리즘에 대한 설명이 궁금하다면 아래 링크를 확인하면 된다.

https://pledge24.tistory.com/191

문제 1967. 트리의 지름(에센셜 4)

정답 코드 

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

struct weight_data
{
    int node_no;
    int weight;
};

vector<vector<weight_data>> nodes;
vector<bool> visited;

int N; 
int max_length = -1;

int dfs(int node_no){
  
    vector<int> length;   
    bool find = false;
    for(weight_data next_node : nodes[node_no]){
        if(!visited[next_node.node_no]){
            find = true;
            visited[next_node.node_no] = true;
            length.push_back(dfs(next_node.node_no) + next_node.weight);
        }
        
    }

    if(!find) return 0;

    sort(length.begin(), length.end(), greater<int>());
    
    if(length.size() >= 2){    
        max_length = max(max_length, length[0]+length[1]);
    }
   
    return length[0];
}

bool cmp(const weight_data &a, const weight_data &b){
    return a.node_no < b.node_no;
}
int main() {
	fastio;
    cin >> N;

    nodes.resize(N+1);
    visited.resize(N+1);

    int node1, node2, weight;
    for(int i = 0; i < N; i++){
        cin >> node1;

        while(1){
            cin >> node2;
            if(node2 == -1) break;
            cin >> weight;
            nodes[node1].push_back({node2, weight});
            
        }     
        
        sort(nodes[node1].begin(), nodes[node1].end(), cmp);
    }
      
    vector<int> length;
    visited[1] = true;
    for(weight_data next_node : nodes[1]){
        visited[next_node.node_no] = true;
        length.push_back(dfs(next_node.node_no) + next_node.weight);
    }
    sort(length.begin(), length.end(), greater<int>());


    if(length.size() >= 2){
        max_length = max(max_length, length[0]+length[1]);
    }
    else{
        max_length = max(max_length, length[0]);
    }

    cout << max_length << '\n';
}

 

더 좋은 코드?

...?