[알고리즘] Not Shading

구현 방식

• 최장거리를 만드는 노드를 A, B 라고할때
• 한 노드에서부터 가장 먼 노드는 A 또는 B 이다.
• 따라서 한 노드에서부터 가장 먼 노드 V1을 구하고, V1 에서부터 가장 먼 노드 V2 를 구하면
• 그게 바로 최장거리!

#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;
void solution(int N, vector<vector<pair<int, int>>>& graph);
void Init(int N);
void dfs(int start, vector<vector<pair<int, int>>>& graph);

int dist[10001];
int maxDistIdx = -1;
int maxDist = INT_MIN;

int main()
{
    int N;
    cin >> N;
    vector<vector<pair<int,int>>> graph = vector<vector<pair<int, int>>>(N + 1, vector<pair<int, int>>());
    for (int i = 0; i < N-1; i++)
    {
        int from, to, w;
        cin >> from >> to >> w;
        graph[from].push_back({to, w});
        graph[to].push_back({ from, w });
    }

    

    solution(N, graph);
}
void solution(int N, vector<vector<pair<int, int>>>& graph)
{
    int start = 1;
    Init(N);
    dfs(start, graph);
    start = maxDistIdx;
    Init(N);
    dfs(start, graph);

    cout << maxDist << endl;
}

void Init(int N)
{
    fill_n(dist, N + 1, INT_MIN);
    maxDistIdx = -1;
    maxDist = INT_MIN;
}

void dfs(int start , vector<vector<pair<int, int>>>& graph)
{
    stack<int> s;
    s.push(start);
    dist[start] = 0;
    maxDist = 0;
    while (!s.empty())
    {
        int currIdx = s.top();
        s.pop();

        for (pair<int, int> toWeight : graph[currIdx])
        {
            int to = toWeight.first;
            int weight = toWeight.second;
            if (dist[to] == INT_MIN)
            {
                dist[to] = dist[currIdx] + weight;
                s.push(to);
                if (dist[to] > maxDist)
                {
                    maxDist = dist[to];
                    maxDistIdx = to;
                }
            }
        }
    }

}