[PS] 백준 1167 트리의 지름 (c++)

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

1167번: 트리의 지름

오랜만에 알고리즘 트리 문제를 풀어봤습니다. 이 문제는 트리에서 임의의 두 정점 사이의 가장 긴 거리를 출력하는 문제입니다. 

 

입력의 경우 시작 정점(from)이 주어지고, 시작 정점과 연결된 정점(to)과 두 정점 사이의 거리(dist)를 입력으로 받습니다. 더불어 해당 정점에서 입력을 종료하려면 -1을 입력으로 받아야 합니다.

 

첫 번째로, 우선 임의의 정점에서 가장 거리가 먼 노드를 찾습니다. 그 다음, 찾은 노드를 시작 노드로 지정하고 DFS 탐색을 해주면 트리의 지름을 반환할 수 있게 됩니다. 가장 거리가 먼 노드의 위치를 찾는 부분을 찾고 시작 노드로 지정해 주는 부분만 제외하면, 기본적인 DFS 문제와 유사합니다.(임의의 정점과 연결된 노드를 하나씩 방문하여 값을 갱신해줌)

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
int v, from, to, dist, now_node;
int res = 0;
vector<pair<int, int>> graph[100001];
bool visited[100001];

void dfs(int from, int dist)
{
    visited[from] = true;
    
    if (dist > res)
    {
        res = dist;
        now_node = from;
    }
    for (int i = 0; i < graph[from].size(); i++)
    {
        int next_node = graph[from][i].first;
        int next_dist = graph[from][i].second + dist;
        if (!visited[next_node])
        {
            visited[next_node] = true;
            dfs(next_node, next_dist);
            visited[next_node] = false;
        }
    }
}

void findMaxDistanceNodeFromNodeOfFirst()
{
    dfs(1, 0);
}

void initializeMaxDistanceAndVisitStatus()
{
    memset(visited, false, sizeof(visited));
    res = 0;
}

void input()
{
    cin >> v;
    for (int i = 0; i < v; i++)
    {
        cin >> from;
        while (true)
        {
            cin >> to;
            if (to == -1)
                break;
            cin >> dist;
            graph[from].push_back({to, dist});
        }
    }
}

int getDiameterOfTree()
{
    dfs(now_node, 0);
    return res;
}

int main()
{
    input();
    findMaxDistanceNodeFromNodeOfFirst();
    initializeMaxDistanceAndVisitStatus();
    cout << getDiameterOfTree() << '\n';
}