프로그래머스 트리 트리오 중간값

https://school.programmers.co.kr/learn/courses/30/lessons/68937

프로그래머스

 

레벨 4 문제인데 생각보다 할만한 문제입니다.

 

트리가 주어지고, 임의의 정점 (a, b, c) 중에서 a-b, b-c, a-c 3가지 거리의 중간값중 최대값을 구하는 문제입니다.

중간값을 최대화 하고싶은게 목적인데

이것은 a-b, b- c, a-c 이 세개의 값을 최대화 하면 됩니다.

 

모든 정점 3개의 조합을 구해서 거리를 구하며 답을 구하면 시간초과입니다.

 

트리이기 때문에, 어떤 정점에서 다른 정점으로 이동하는 단순경로는 유일합니다.

 

트리에서 어떤 정점에서의 최대거리인 노드는 반드시 지름에 속하는 정점 중 하나입니다.

 

따라서 지름에 속하는 아무 정점 두 개를 구하고 모든 정점을 순회하며 지름에 속하는 두 정점까지의 거리를 구해 최대 중간값을 업데이트 하면 됩니다.

 

코드(c++)

#include <bits/stdc++.h>

using namespace std;
int solution(int n, vector<vector<int>> edges) {
    int answer = 0;
    vector<vector<int>> v(n + 1);
    for (int i = 0 ; i < edges.size(); i++){
        int a = edges[i][0], b = edges[i][1];
        v[a].push_back(b);
        v[b].push_back(a);
    }

    vector<int> dist(n + 1, -1), dist2(n + 1, -1);

    auto dfs = [&](const auto&self, int cur, int prv, int flag) -> void{
        for (int nxt : v[cur]){
            if (nxt == prv) continue;
            if (flag)
                dist[nxt] = dist[cur] + 1;
            else
                dist2[nxt] = dist2[cur] + 1;
            self(self, nxt, cur, flag);
        }
    };
    dist[1] = 0;
    dfs(dfs, 1, 0, 1);
    int mx = 0, idx = 0;
    for (int i = 1; i <= n; i++){
        if (dist[i] > mx){
            mx = dist[i];
            idx = i;
        }
    }
    dist.clear(); dist.resize(n + 1, -1); // 한 지름에서 모든 정점까지 거리
    dist[idx] = 0;
    dfs(dfs, idx, 0, 1);
    mx = 0;
    int idx2 = -1;
    for (int i = 1; i <= n; i++){
        if (dist[i] > mx){
            mx = dist[i];
            idx2 = i;
        }
    }
    dist2[idx2] = 0;
    dfs(dfs, idx2, 0, 0);
    for (int i = 1; i <= n; i++){
        if (i == idx || i == idx2) continue;
        int a = dist[i];
        int b = dist2[i];
        if (a > b){
            answer = max(answer, a);
        }else{
            answer = max(answer, b);
        }
    }

    return answer;
}

 

끗