[1167] 트리의 지름(C++)

문제

바로가기

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

 

 

입력

트리가 입력으로 주어진다.

먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.

예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.

각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

 

출력

첫째 줄에 트리의 지름을 출력한다.

 

 

알고리즘

• 그래프
• 트리
• DFS

 

 

해결 방법

[1967] 트리의 지름 문제와 정말 유사하다.

입력 형식만 좀 다를뿐, 풀이 방법은 거의 똑같다고 보면 된다.

 

하나 차이가 있다면, [1967] 트리의 지름 문제는 루트 노드, 부모 노드, 자식 노드라는 개념이 사전에 설정되어있고 입력도 부모-자식 관계로 주어진다.

반면 이 문제의 경우 루트도 따로 없고 부모-자식 개념도 없다.

 

그럼 어떻게 하면 될까? 간단하다.

없는 루트를 내가 임의로 만들어주면 된다.

나는 임의의 루트를 1번이라고 했는데, 다른 노드로 해도 상관은 없다.

 

이 문제를 풀기 위해서도 dfs를 두 번만 수행하면 된다.

첫번째 bfs는 루트 노드에서 가장 멀리 떨어진 노드(지름의 한쪽 끝)를 찾기 위함이고,

두 번째 bfs는 위에서 찾은 지름의 한쪽 끝에서 시작하여 지름의 반대쪽 끝과 지름의 길이를 찾기 위함이다.

 

끝!

 

 

내 코드

// [1167] 트리의 지름
// 유사문제: [1967] 트리의 지름
// bfs
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool visited[100001];
int V, diameter, endNode, connect[100001];
vector<pair<int, int>> vec[100001];

void input()
{
    int n1, cost, num;
    cin >> V;
    for(int i = 0; i < V; i++) {
        cin >> n1;
        while(true) {
            cin >> num;
            if(num == -1) break;
            else {
                cin >> cost;
                connect[n1]++;
                vec[n1].push_back({num, cost});
                vec[num].push_back({n1, cost});
            }
        }
    }
}

void dfs(int node, int cost)
{
    visited[node] = true;
    if(cost > diameter) {
        diameter = cost;
        endNode = node;
    }
    for(int i = 0; i < vec[node].size(); i++) {
        int next = vec[node][i].first;
        if(!visited[next]) {
            dfs(next, cost + vec[node][i].second);
        }
    }
}

void solve()
{
    dfs(1, 0); // 지름 한쪽 끝 찾기
    diameter = 0;
    memset(visited, false, sizeof(visited));
    dfs(endNode, 0); // 반대쪽 지름 끝 & 지름 찾기
    cout << diameter << '\n';
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    solve();

    return 0;
}