[백준 C++] 19581 두 번째 트리의 지름

문제

트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다.

트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리는 두 번째 트리의 지름을 구하려고 한다.

두 번째 트리의 지름은 무엇이냐? 바로 두 번째로 가장 먼 두 정점 간의 거리를 의미한다. (두 번째 트리의 지름은 트리의 지름과 같을 수 있다.)

바로 두 번째 트리의 지름을 구해보자.

입력

첫 번째 줄에는 정점의 개수 N(3 ≤ N ≤ 100,000)이 들어온다.

둘째 줄부터 N번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수와 두 번째 정수는 간선과 연결된 정점 번호를 나타내고, 세 번째 정수는 간선의 가중치를 나타낸다. 간선의 가중치는 20,000 이하의 자연수이다.

출력

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

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

풀이

1. 임의의정점으로 부터 가장 먼 거리(가중치)의 정점a를 구한다.
2. 정점a로부터 가장 먼 정점b를 구한다.
3. 정점a로부터 정점b를 제외한 가장 먼 정점간의 거리를 구한다.
   4.정점b로부터 정점a를 제외한 가장 먼 정점간의 거리를 구한다.
4. 3과4의 거리값중 가장 큰값을 출력한다.

문제풀이에 도움이 됬떤 포스팅이있다.. >> https://mangu.tistory.com/147
참고했습니다. 감사합니다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define MAX 100001
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort; using std::max; using std::min;
using std::make_pair; using std::max_element; using std::min_element;
using std::fill;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<int, double> pid;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef pair<string, string> pss;

int N;
vector<pii> edge[MAX]; //간선 정보, 가중치
bool visited[MAX];
ll weight[MAX]; //정점
void init();
void func();
pil bfs(int n, int remove=0);
void init() {
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int ver1, ver2, value;
        scanf("%d%d%d", &ver1, &ver2, &value);
        edge[ver1].push_back({ ver2, value });
        edge[ver2].push_back({ ver1, value });
    }
}

void func() {
    int a = bfs(1).first; //임의정점으로부터 가장 먼 정점a를 구함
    int b = bfs(a).first; //정점a로 부터 가장 먼 정점b를 구함
    //정점a로부터 가장먼 정점b를 제외한 그다음 정점까지의 거리를 출력
    printf("%lld", max(bfs(a, b).second, bfs(b, a).second));
}

//점 n에서 가장 먼 점의 번호와 두 정점사이 거리를 리턴
//remove:제외할 정점 
pil bfs(int n, int remove) {
    fill(visited, visited + N + 1, false);
    fill(weight, weight + N + 1, 0);
    queue<int> q;
    q.push(n);
    visited[n] = true;
    visited[remove] = true; //제외할정점은 미리 체크
    int max = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < edge[v].size(); i++) {
            int vv = edge[v][i].first;
            int value = edge[v][i].second;
            //printf("%d >> vv:%d, visited[vv]:%d   weight[vv]:%lld\n", v, vv, visited[vv], weight[vv]);
            if (visited[vv]) continue;
            visited[vv] = true;
            //다음 정점의 거리는 두정점간의 가중치 + 현재정점의 가중치
            weight[vv] = value + weight[v];
            q.push(vv);
            //printf(">>>>>>>>weight[vv]:%lld\n", weight[vv]);
        }
    }

    ll* res = max_element(weight + 1, weight + N + 1);//구한 모든 거리값중 큰값을 참조
    return { res - weight , *res }; 
}

int main(void) {
    init();
    func();


    return 0;
}