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

문제 이해

- 트리의 지름: 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것

- 트리의 지름을 구하라

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 256MB

 

<입력>

- V: 정점의 개수 (2 ~ 100,000, 10^5)

- V개의 줄에 걸쳐 간선의 정보(시작 정점, 종료 정점, 정점까지의 거리)

※ 거리 (1 ~ 10,000, 10^4)

※ 각 줄의 마지막에는 -1이 입력으로 들어온다.

 

<출력>

- 트리의 지름을 출력하라.

 

 

---

문제 풀이

이 문제는 트리의 지름과 관련된 정보를 알아야 풀 수 있다.

임의의 정점에서 거리가 가장 먼 정점은 지름을 구성하는 한 정점이다.
또한 지름을 구성하는 정점에서 거리가 가장 먼 정점또한 지름을 구성하는 정점이다.

 

위 정보만 알고 있다면 다들 쉽게 푸실거라 생각한다.

 

 

---

주의할 점

1. 인접 그래프에 입력값을 넣을 때 주의하자.

 

이 문제는 정점과 이어진 간선들의 정보에 대해서 모두 알려주는데,

그렇기에 각 시작정점에서 종료정점까지 입력받은 뒤 양방향으로 넣어줄경우 중복해서 넣는 셈이 된다.

 

 

이 경우, 시간 초과가 뜰 수 있다.

 

꼭 단방향으로만 넣어주자.

for(int i = 0; i < v; i++){
        int start;
        cin>>start;

        while(true){
            int point, line;
            cin>>point;
            if(point == -1) break;

            cin>>line;
            arr[start].push_back({point, line});
        }
    }

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 987654321

vector<pair<int, int>> arr[101010];
int mymax = -1, myend;

void dfs(int now, int prev, int sum){
    if(mymax < sum){
        mymax = sum;
        myend = now;
    }

    for(auto i : arr[now]){
        int next = i.first;
        if(next != prev){
            dfs(next, now, sum + i.second);
        }
    }
}

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

    int v;
    cin>>v;
    for(int i = 0; i < v; i++){
        int start;
        cin>>start;

        while(true){
            int point, line;
            cin>>point;
            if(point == -1) break;

            cin>>line;
            arr[start].push_back({point, line});
        }
    }

    dfs(1, 0, 0);
    dfs(myend, 0, 0);

    cout<<mymax;
    
    return 0;
}

 

 

 

---

배운 점

1. 인접 그래프에서 DFS의 시간 복잡도는 O(V+E)라는 걸 배웠다. (V: 정점의 개수, E: 간선의 개수)

2. vector 자료형에서 auto의 사용법을 숙지했다.

3. 트리 문제에서 visited 배열을 사용하지 않고 푸는 방법을 배울 수 있었다.