백준 1167 트리의 지름

트리를 받아. 트리에서 나올 수 있는 가장 긴 거리(트리의 지름)를 구하는 문제이다. 

원래 구현은 각 노드에서 DFS를 해 그 중에서 가장 긴 값을 구하는 코드를 작성했다. 우왕 탐색코드만 짜고 돌기만 하면 되네! 했는데 당연하게도 타임아웃이 떴다.

 

가장 긴 길이를 더 빠르게 구할 방법이 없을까 했는데 질문들을 보니 2번이면 계산이 가능하다고 한다.

머리로 여러번 생각해봤는데, 도저히 답이 안나와서 한걸음 떨어져서 생각해보니 그래프와 트리를 막 섞어서 생각하고 있었다. 트리의 경우, 무조건 어느 노드는 말단이 있다. 일단 아무 노드에서 가장 먼 노드를 구하고, 거기서부터 가장 먼 거리를 구하면 그게 바로 트리에서 나올 수 있는 가장 긴 거리이다.

 

그러면 2번만에 된다는 말이 맞다. 첫번째는 가장 멀리 있는 노드를 구하고, 두번째는 그 노드에서부터 가장 긴 거리를 구한다.

 

DFS 재귀함수는, 어떤 노드에서 자식들을 전부 탐색하며 스스로를 실행한다. 자식들 탐색한 값 중에서 max_cost와, 그 노드를 받아 리턴하게 된다. 말단 노드의 경우, cost는 0, 노드는 자신을 리턴한다. 함수에서는 각 말단에서부터 거기까지 연결 비용, 해당 노드 인덱스를 받아 최대값을 가지는 것만 리턴한다.

 

원래 cost만 구하는 함수를 만들었지만, pair를 리턴하도록 하여 가장 긴 경로를 가지는 말단 노드도 리턴하게 했다. Python의 경우 여러개 값을 리턴하는게 자연스러웠지만 C계열 언어에서는 어떻게 하지... 순간 굳었다. 안해봐서 그랬다. 방법은 많은데. struct를 써도 되고 pair를 써도 되고...(뭐 어차피 pair가 struct긴 하지만.)

 

그것 외에는 탐색을 하기만 하면 되는 문제였다.

트리에서 가장 긴 거리를 구할 때의 방법. 그 아이디어가 문제다.

---

#include <iostream>
#include <vector>


std::pair<int, int> getMaxCost(int node, int prev, std::vector<std::pair<int, int> > adj[])
{
    int max_cost = -1;
    int max_node;
    for (int i =0; i < adj[node].size(); i++)
    {
        int next = adj[node][i].first;
        if (next == prev)
            continue;
        std::pair<int, int> temp_pair = getMaxCost(next, node, adj);
        if (max_cost < temp_pair.first + adj[node][i].second)
        {
            max_cost = temp_pair.first + adj[node][i].second;
            max_node = temp_pair.second;
        }
    }
    if (max_cost == -1)
        return std::make_pair(0, node);
    else
        return std::make_pair(max_cost, max_node);
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    int N;
    std::cin >> N;

    std::vector<std::pair<int, int> > adj[N];

    for (int i = 0; i < N; i++)
    {
        int v;
        std::cin >> v;
        v--;
        while (1)
        {
            int inp1, inp2;
            std::cin >> inp1;
            if (inp1 == -1)
                break;
            inp1--;
            std::cin >> inp2;
            adj[v].push_back(std::make_pair(inp1, inp2));
        }
    }
    // std::cout << getMaxCost(0, -1, adj);
    std::pair<int, int> find_max_dist = getMaxCost(0, -1, adj);

    std::pair<int, int> find_max_cost = getMaxCost(find_max_dist.second, -1, adj);
    // int maxCost = -1;
    // for (int i = 0; i < N; i++)
    // {
        
    //     std::pair<int, int> temp = getMaxCost(i, -1, adj);
    //     std::cout << "node " << i+1 << " to " << temp.second + 1 << " : " << temp.first << '\n';
    // }
    std::cout << find_max_cost.first;
}

 

이 문제는 뭔가 다양한 고찰이 있던 문제다. 문제를 대하는 내 태도에 대해 뭔갈 깨달았다. 문제를 봤을때, 성급하게 이렇게해봐야지! 하고 시행착오를 겪는것도 중요하지만, 차분히 어떤 방법이 좋을까 생각하는 것도 좋을 것 같다.

마음을 급하게 먹으면 그 pair를 떠올릴때처럼 순간 굳을 때도 있다. 급한건 이해되지만, 급하다고 해서 문제가 빨리 풀리는건 아닌것 같다.

차분히 적어가며 풀기.

 

오늘도 평온한 하루가 되길. 슨민.