[Algorithm]Baekjoon 1967번 :: 트리의 지름

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

1967번: 트리의 지름

struct Node
{
    int node;
    int weight;
};
 
vector<vector<Node>> graph(10000);
int start;
vector<int> v;
 
int getMaxChild(int n, int weight)
{
    int result = 0;
 
    for (int i = 0; i < graph[n].size(); i++)
    {
        if (n == start)
        {
            v.push_back(getMaxChild(graph[n][i].node, graph[n][i].weight));
        }
        else
        {
            result = max(result, getMaxChild(graph[n][i].node, graph[n][i].weight));
        }
    }
 
    if (n == start)
    {
        if (graph[n].size() == 0) return 0;
 
        sort(v.rbegin(), v.rend());
 
        if (v.size() >= 2)
        {
            return v[0] + v[1];
        }
        else
        {
            return v[0];
        }
    }
 
    return result + weight;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    int a, b, c;
    cin >> n;
 
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
    }
 
    int result = 0;
 
    for (int i = 1; i <= n; i++)
    {
        v.clear();
        start = i;
        result = max(result, getMaxChild(i, 0));
    }
 
    cout << result;
}
 

효율이 좋은 로직이 생각나지 않아 일단 각 정점기준으로 자식노드들의 최대값을 얻은 후, 자식이 두개이상이면 큰값 두개를 더하고 자식이 1개면 큰값 한개를 리턴하게 하는식으로 일일이 각 정점에서의 최대값을 구해봤다.

거의 반 완전탐색이긴한데 다행히 통과는 했다. 다만 440ms로, 딱봐도 효율은 좋지 않다.

 

다른사람 풀이를 참고하니, 탐색 두번으로 충분히 풀리는 문제였다.

먼저 임의의 노드에서 가장 먼 노드를 먼저 찾는다.

여기서 임의의 노드란, 만약 어떤 테스트케이스의 정점개수가 5개라면 1번노드에서 가장 먼 노드를 찾든, 2번노드에서 가장 먼 노드를 찾든 3번에서든 아무 상관 없다.

왜냐하면 일단 어디노드에서든 가장 먼 지점을 찾는다면 해당 노드는 반드시 양 끝단 중 하나이기 때문이다.

실제로 위 코드에서 시작을 1로 안하고 2로해도 통과가 뜬다.

그리고 위의 과정을 통해 구한 끝노드에서 다시 한번 더 가장 먼 거리의 노드를 찾아서 출력하면 끝.

 

순서를 요약하자면, 

1. 지름이 가장 길었을때 형태의 끝노드 두개중 하나를 먼저 구해준다. 

    구하는 방법으로는 임의의 노드에서 가장 먼 노드가 해당노드이다.

 

2. 1번에서 구한 노드를 기준으로 가장 먼 노드를 구해서 길이를 출력하면 끝.

     1번에서구한노드 == 양끝단 노드 중 하나

     2번에서 구한 노드 == 양끝단 노드 중 마지막 하나.

 

BFS로 탐색했고 코드는 아래와 같다.

 

struct Node
{
    int node;
    int distance;
};
 
vector<vector<Node>> graph(10001);
 
Node BFS(int start)
{
    bool visited[10001] = { false };
    visited[start] = true;
 
    queue<Node> q;
    q.push({ start,0 });
 
    int maxDistance = 0;
    int maxNumNode = 0;
 
    while (!q.empty())
    {
        Node popedNode = q.front();
        q.pop();
 
        int curNode = popedNode.node;
        int curDistance = popedNode.distance;
 
        if (curDistance > maxDistance)
        {
            maxDistance = curDistance;
            maxNumNode = curNode;
        }
 
        for (int i = 0; i < graph[curNode].size(); i++)
        {
            int nextNode = graph[curNode][i].node;
            int nextDistance = curDistance + graph[curNode][i].distance;
 
            if (visited[nextNode]) continue;
            
            visited[nextNode] = true;
            q.push({ nextNode,nextDistance });
        }
    }
 
    return { maxNumNode,maxDistance };
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    int a, b, c;
 
    cin >> n;
 
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
 
    cout << BFS(BFS(1).node).distance;
}

 

 

4ms가 BFS로 푼 코드이다.