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

프로그래머스

N개의 점으로 이루어진 트리에서 3개의 임의의 점 A, B, C를 선택합니다. 이때, A와 B의 거리, A와 C의 거리, B와 C의 거리중 중간 값을 반환하는 함수를 F라고 부를 때, 힘수 F를 통해 반환 받을 수 있는 수들 중 가장 큰 값을 구해주세요.

 

 

풀이 방법

중간 값을 평균값으로 오해하면 안됩니다. 중간값은 임의의 점 3개 사이의 거리 (A->B, A->C, B->C)를 정렬 했을 때, 2번 째에 오는 수를 의미합니다. 중간 값을 찾기 위해서는 트리의 가장 큰 지름을 찾아야 합니다. 

 

가장 큰 지름을 찾자

특정 노드에서 시작한 지름들 중 가장 큰 지름이 2개 이상이 나온다고 하면 정렬 할 때

(중간 노드는 생략하고 길이가 5인 노드가 있다는 가정)

K와 G의 거리가 뭐가 나오든 중간 값은 항상 5가 됩니다

 

 

특정 노드에서 시작한 지름들 중 가장 큰 지름이 1개가 나온다면  ( A->D가 3으로 가장 큼 )

A->D 다음으로 큰 A->C의 거리가 무조건 중간 값이 됩니다.

 

 

정리하자면 노드를 순회하며 가장 긴 지름을 찾고 위의 조건대로 중간값을 출력하면 되겠습니다.

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, vector<int>> trees;
unordered_map<int, vector<int>> tree_length;
bool visit[250002];
int max_step = -1;


// 가장 긴 노드 찾는 함수
void find_path(int vtx, int step)
{
    visit[vtx] = true;
    if (max_step <= step)
    {
        max_step = step;
        tree_length[max_step].push_back(vtx);
    }
    
    for (int idx : trees[vtx])
    {
        if (!visit[idx])
            find_path(idx, step+1);
    }
    
    visit[vtx] = false;
}

int solution(int n, vector<vector<int>> edges) {
    
    // 트리 구성
    int answer = 0;
    for (auto& edge : edges){
        trees[edge[0]].push_back(edge[1]);
        trees[edge[1]].push_back(edge[0]);
    }
    
    임의의 노드에서부터 지름 탐색
    find_path(1, 0);
    for (int i = 0; i < 2; i++)
    {
    	// 가장 멀리 있는 노드에서 다시 길이 탐색
        int nxt = tree_length[max_step][0];
        max_step = -1;
        tree_length.clear();
        find_path(nxt, 0);
        
        // 같은 길이의 노드가 두개 이상이라면 중간값은 항상 지름
        if (tree_length[max_step].size() > 1)
            return max_step;
            
        // 만약 가장 긴 지름의 노드가 1개였다면, 반대편에서도 실행
    }
    
    // max_step의 길이가 
    return max_step-1;
}