[백준 / BOJ] C++ 1967 트리의 지름

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

1967번: 트리의 지름

풀이

깊이우선탐색(DFS)를 이용한 문제이다.

 

백준 문제를 풀다보면 자주자주 나오는 유형의 문제이다.

그래도 이 문제는 가장 끝 노드와 그 해당 노드로 부터 가장 멀리 떨어진 노드를 찾는다는 

조건이 주어지기 때문에 비교적 쉽게 문제 풀이가 가능하다.

 

조건의 시작점은 트리의 시작 노드에서 부터 가장 멀리 떨어진 노드이다. (DFS 탐색 첫번째)

조건의 끝점은 시작노드로 부터 가장 멀리 떨어진 노드에서 부터 가장 멀리 떨어진 노드이다. (DFS 탐색 두번째)

 

총 깊이우선탐색을 2번 하여 두점의 총 가중치를 구한다.

 

비교적 간단한 문제이고, 아래는 C++로 구현된 코드이다.

 

Code ( C++ )

#include <iostream>
#include <vector>
#define MAX 10001

using namespace std;

bool isVisit[MAX];
int N;
int MaxN, MaxWeight;
struct NODE
{
    int node;
    int weight;
};

vector<NODE> vec[MAX];

void DFS(int idx, int weight)
{
    if(isVisit[idx] == true)
        return;

    isVisit[idx] = true;

    if (weight > MaxWeight)
    {
        MaxWeight = weight;
        MaxN = idx;
    }

    for (int i = 0; i < vec[idx].size(); i++)
    {
        int next_node = vec[idx][i].node;
        int next_weight = vec[idx][i].weight + weight;
        DFS(next_node, next_weight);
    }
}

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

    // 부모노드, 자식노드, 가중치
    int parent, child, weight;

    cin >> N;

    for(int i = 0; i < N - 1; i++)
    {
        cin >> parent >> child >> weight;
        vec[parent].push_back({child,weight});
        vec[child].push_back({parent, weight});
    }

    // 시작 노드는 항시 1이고, 1이 헤드이기에 가중치 0
    DFS(1, 0);

    // 이후 초기화
    memset(isVisit, 0, sizeof(isVisit));

    // 시작지점에서부터 가장 먼 정점을 찾았으니,
    // 그 해당 정점에서 가장 먼 정점 찾기. 가중치 초기화
    MaxWeight = 0; DFS(MaxN, 0);

    cout << MaxWeight;
}