1167번

1167번 - 트리의 지름

트리의 지름에 대한 개념이 하나도 없이 문제를 풀었다.

모든 노드에 대해서 DFS를 통해 최대값을 구하는 완전탐색 방식으로 접근했다.

근데 역시나 노드의 최대값이 100000이라는 한계를 뚫지 못하고 시간 초과로 나왔다.

사실 풀때도 이미 이거 시간이 너무 오래 걸리겠는데? 라는 생각을 했지만...

그래서 DP로 가능할까 했더니 DP로 불가능해 보였고, 

시간을 줄이기 위해서 leaf node , 즉 연결된 노드가 1개 밖에 없는 노드만을 돌려도 보았다.

(2개 이상의 노드에서 dfs를 수행할 경우, 그 길이는 구한 최대값에서 다른 노드로 가는 가중치를 더하면 되므로, 최대값이 될 수 없기에)

하지만 아무리 용을 써도 시간초과는 벗어날 수 없었다.

그래서 트리의 지름의 길이를 알아보니, 그것을 구할 수 있는 방법이 있었다.

1. 아무 점에서 가장 멀리있는(가중치가 가장 큰) 노드 A를 찾는다. 그렇다면 이 노드가 트리의 지름의 한 점이 된다.

2. 그래서 다음으로 이 노드 A에서 가장 멀리 있는 (가중치가 가장 큰) 다른 노드를 찾으면, 그 노드를 B라 했을 때 A-B 의 거리가 트리의 지름이 된다.

사실 1번이 나는 직관적으로 이해하는게 너무나 어려웠다.

궁금한 사람은 구글링을 통해서 증명하는 방법을 찾아보는게 좋은 것 같다. 나도 종만북을 통해 다시 한번 봐야겠다. 

<정답 코드 - DFS,BFS (사용하지 않는 함수 주석처리) >

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int N;
vector<pair<int, int>> v[100001];
int sum, ans;
bool check[100001];
int dist[100001];
int endpoint1;
void dfs(int now)
{
    check[now] = true;
 
    for (int i = 0; i < v[now].size(); i++)
    {
        int next = v[now][i].first;
        int price = v[now][i].second;
 
        if (!check[next])
        {
            sum += price;
            if (ans < sum)
            {
                ans = sum;
                endpoint1 = next;
            }
            dfs(next);
            sum -= price;
        }
    }
 
    return;
}
void bfs(int x)
{
    queue<int> q;
    q.push(x);
    check[x] = true;
    dist[x] = 0;
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int price = v[now][i].second;
 
            if (!check[next])
            {
                dist[next] = dist[now] + price;
                if (ans < dist[next])
                {
                    ans = dist[next];
                    endpoint1 = next;
                }
                check[next] = true;
                q.push(next);
    
            }
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        int start;
        cin >> start;
        int a, b;
        while (true)
        {
            cin >> a;
            if (a == -1) { break; }
            cin >> b;
            v[start].push_back(make_pair(a, b));
        }
    }
 
    //노드 1에서 노드 A 찾기
    memset(check, false, sizeof(check));
    sum = 0;
    //dfs(1);
    bfs(1);
 
    //노드 A에서 노드 B 찾기
    memset(check, false, sizeof(check));
    sum = 0;
    ans = 0;
    //dfs(endpoint1);
    bfs(endpoint1);
        
    cout << ans << endl;
    return 0;
}