[백준] 1167번 : 트리의 지름

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 트리 자료구조 문제로, 문제 제목에서부터 알 수 있듯이 주어지는 트리에 대한 트리의 지름, 즉 가장 먼 두 정점 사이의 거리를 구하는 문제이다.

1) edges 벡터에 각 노드의 인접 노드들에 대한 데이터를 입력 받아 pair(인접 노드 번호, 거리)로 저장한다. 그리고 임의 정점에서 dfs()를 실행했을 때 해당 정점으로부터 다른 정점까지의 거리를 저장하기 위한 n 크기의 dist 벡터를 선언하고 전부 -1로 초기화한다.

2) 임의의 정점에 대해 dfs()를 실행한다.

• 현재 순서 노드와 시작 정점 사이의 거리를 dist[헌재 노드]에 저장한다.
• 만약 위 거리가 지금까지의 maxDist(임의 정점에서 다른 정점까지 거리 중 가장 먼 거리)보다 길다면 해당 거리를 maxDist로 갱신하고, farNode(가장 먼 정점)에 현재 순서 노드를 저장한다.
• edges[현재 노드]를 탐색해 아직 방문하지 않은 인접 노드에 대해 dfs()를 재귀 호출한다.

3) 위 임의의 정점에 대한 dfs()가 완료되면 farNode에는 임의 정점으로부터 가장 먼 정점이 저장된다.

4) maxDist와 dist 벡터를 처음 상태로 초기화 한 뒤, 이제 아까 구한 임의 정점으로부터 가장 먼 정점(farNode)에 대해 dfs()를 실행해 farNode로부터 가장 먼 정점을 구한다.

5) 위 dfs()가 완료된 후에 maxDist에는 farNode로부터 가장 먼 정점 사이의 거리가 저장되어있고, 이것이 트리의 지름이 된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
typedef pair<int, int> pii;
vector<vector<pii>> edges;
vector<long long> dist;
int maxDist = 0;
int farNode;
int dia_node;

void DFS(long long distance, int currentNode)
{
    dist[currentNode] = distance;
    if (dist[currentNode] > maxDist)
    {
        maxDist = dist[currentNode];
        farNode = currentNode;
    }
        
    for (int i = 0; i < edges[currentNode].size(); i++)
    {
        int nextNode = edges[currentNode][i].first;

        if (dist[nextNode] == -1)
            DFS(distance + edges[currentNode][i].second, nextNode);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    
    int n;
    cin >> n;

    edges.resize(n);
    dist.assign(n, -1);

    for (int i = 0; i < n - 1; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;

        edges[a - 1].push_back(pii(b - 1, w));
        edges[b - 1].push_back(pii(a - 1, w));
    }

    DFS(0, 0);
    dia_node = farNode;

    maxDist = 0;
    dist.assign(n, -1);
    DFS(0, dia_node);
    cout << maxDist;
}