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

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

1167번: 트리의 지름

struct Node
{
    int node;
    int distance;
};
 
vector<vector<Node>> graph(100001);
bool visited[100001] = { false };
 
int n, a, b, c;
int maxDistance;
int maxDistanceNode;
 
pair<int, int> BFS(int n) // 노드,거리
{
    memset(visited, false, sizeof(visited));
    maxDistance = 0;
    maxDistanceNode = 0;
 
    queue<Node> q;
    visited[n] = true;
    q.push({ n,0 });
 
    while (!q.empty())
    {
        int curNode = q.front().node;
        int curDistance = q.front().distance;
        q.pop();
 
        if (curDistance > maxDistance)
        {
            maxDistance = curDistance;
            maxDistanceNode = curNode;
        }
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextDitance = graph[curNode][i].distance + curDistance;
 
            if (visited[nextNode]) continue;
 
            q.push({ nextNode,nextDitance });
            visited[nextNode] = true;
        }
    }
 
    return { maxDistanceNode,maxDistance };
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
 
        while (1)
        {
            cin >> b; 
            if (b == -1) break;
            cin >> c;
 
            graph[a].push_back({ b,c });
        }
    }
 
    cout << BFS(BFS(1).first).second;
}

저번에 풀었던 골드4짜리 트리의지름 문제랑 거의 동일하다.

입력받는거 조금 다른것과 정점개수가 10만개가 됐다는거 말고는, 사실상 같은 문제라서 똑같이 코드짜서 제출했더니 통과했다.

 

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

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

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

 

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

굳이 이전에 풀었던 골드4짜리와의 차이점이라면, 말했듯이 정점개수가 더 많아졌기 때문에 위의 로직이 아니라 약간 브루트포스식으로 코드를 짰다면 골드4짜리에서는 통과가 됐었을 수도 있겠지만 이 문제에서는 반드시 시간초과가 나왔을것이다.