1967번

1967번 - 트리의 지름

1167 이랑 똑같은 문제이다.

1167번은 입력에서 그래프의 양쪽이 연결되어서 주어졌는데,

1967번 같은 경우는 한쪽 방향의 연결만 주어지므로 , 그것만 바꾸면 정답이 된다.

참, 그리고 N의 범위도 더 줄어들었다.

DFS, BFS 모두 사용해서 풀 수 있다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int N;
vector<pair<int, int>> v[10001];
int sum, ans;
bool check[10001];
int dist[10001];
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-1; i++)
    {
        int start,end, weight;
        cin >> start>>end >> weight;
        v[start].push_back(make_pair(end, weight));
        v[end].push_back(make_pair(start, weight));
    }
 
    //노드 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;
}