[프로그래머스][level4] 트리 트리오 중간값 (C++)

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

코딩테스트 연습 - 트리 트리오 중간값

 

 

[난이도] level4
[유형] 트리

[풀이]
트리의 지름을 이용하여 해결하는 문제입니다.
트리의 지름이란 트리에서 가장 먼 두 점 a,b의 경로를 의미합니다.
임의의 점 x에서 가장 먼 점 y를 구하고 y에서 가장 먼 점 z를 구하면 y-z의 경로가 트리의 지름이 됩니다.
( https://blog.myungwoo.kr/112 블로그를 참고하시면 자세한 설명이 있습니다.)

문제의 주어진 트리에서 지름이 y-z1, y-z2 이렇게 두가지가 있다면
정답은 트리의 지름의 길이가 됩니다. 왜냐하면 세 점을 y , z1, z2 이렇게 정하면
z1-z2의 거리는 트리의 지름인 y-z1,y-z2보다 길어질 수 없기 때문에 y-z1의 길이가 무조건 중간값이 됩니다.

만약 트리의 지름이 y-z 한개밖에 나오지 않는다면 z에서 다시한번 트리의 지름을 구해봅니다.
만약 이때 위의 경우처럼 두가지가 나온다면 마찬가지로 트리의 지름의 길이가 중간값이 되고,

만약 이때도 한가지만 나온다면 (트리의 지름의 길이 -1)이 정답이 됩니다.
왜냐하면 트리의 지름이 단 한가지 경로만 존재하는 경우이며 이것보다 같거나 긴 경로는 없습니다.
그러므로 트리의 지름 y-z 에서 z와 인접한 점 w를 정해야 하는 나머지 한 점으로 설정하면
y-w-z 형태의 경로가 나오게 되고, y-z,y-w,w-z 중에 y-w가 (y-z의 길이 -1)로, 구해야 하는 중간값이 됩니다.

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[250001];
priority_queue<int> pq;
int mxD,from;
void dfs(int p,int m,int cnt,bool f){
    if(mxD < cnt){
        mxD=cnt;
        from=m;
    }
    if(f && adj[m].size()==1) pq.push(cnt);
    for(auto nxt : adj[m])
        if(nxt!=p) dfs(m,nxt,cnt+1,f);
}
int solution(int n, vector<vector<int>> edges) {
    for(auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    dfs(0,1,0,0);

    int a = from; mxD=0;
    dfs(0,a,0,1);
    int t=pq.top(); pq.pop();
    if(t==pq.top()) return t;
    while(!pq.empty()) pq.pop();

    a=from; mxD=0;
    dfs(0,a,0,1);
    t=pq.top(); pq.pop();
    return t==pq.top() ? t : t-1;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/트리_트리오_중간값.cpp