[백준/Baekjoon] 1967 트리의 지름 C++ :: DFS

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

1967번: 트리의 지름

---

1. Logic

트리의 지름을 구하는 방법은 먼저 임의의 한 점에서 가장 거리가 먼 노드를 탐색한다. 이후 가장 거리가 먼 노드에서부터 다시 한번 가장 거리가 먼 노드를 탐색했을 때 거기가 트리의 지름이 된다.

---

 

 

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
vector<pair<int, int>> tree[10001];
bool vis[10001];
int deepestNode;
int dia;

void DFS(int cur, int cost) {
    if(dia < cost) {
        dia = cost;
        deepestNode = cur;
    }

    vis[cur] = true;

    for(int i = 0; i < tree[cur].size(); i++) {
        int next = tree[cur][i].first;
        int nCost = tree[cur][i].second;

        if(vis[next]) continue;

        DFS(next, cost + nCost);
    }
}

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

    for(int i = 0; i < n-1; i++) {
        int start, end, value;
        cin >> start >> end >> value;

        tree[start].push_back({end, value});  
        tree[end].push_back({start, value});    
    }

    DFS(1, 0);
    dia = 0;
    memset(vis, false, sizeof(vis));

    DFS(deepestNode, 0);
    cout << dia;
}

 

---

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90