백준 No.1167 [트리의 지름]

백준 No.1167 [트리의 지름]

---

  문제 

1167번: 트리의 지름 (acmicpc.net)

1167번: 트리의 지름

---

  설명 

 <알고리즘 분류> 
 * DFS

백준 No.1967 [트리의 지름] (tistory.com)

백준 No.1967 [트리의 지름]

  현재 이 문제는 위 링크에서 설명되는 1967번 [트리의 지름] 문제와 정점의 개수 / 간선의 가중치의 범위와 정점, 간선이 입력되는 방식 말고는 다를게 없는 문제이다. 트리의 지름을 구하는 접근 방식은 100.00 % 동일하다.

---

  Code 

#include <iostream>
#include <vector>
#include <cstring>
#define N 100001

using namespace std;

struct s1 {
    int nxt;
    int dist;
};

int n;
int maxVal = 0;
int maxNode = 0;
vector<s1> nodes[N];
bool visit[N];

void dfs(int cur, int val) {
    visit[cur] = true;

    if (maxVal < val) {
        ::maxVal = val;
        ::maxNode = cur;
    }

    for (int i = 0; i < nodes[cur].size(); i++) {
        int nxt = nodes[cur][i].nxt;

        if (!visit[nxt])
            dfs(nxt, val + nodes[cur][i].dist);
    }
}

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

    cin >> n;

    int cur = 0;
    int nxt = 0;
    int dis = 0;

    for (int i = 1; i <= ::n; i++) {
        cin >> cur;

        while (cin >> nxt && nxt != -1) {
            cin >> dis;
            nodes[cur].push_back({nxt, dis});
        }
    }

    dfs(1, 0);          // 1번 정점에서 가장 먼 정점을 탐색
    memset(visit, false * sizeof(bool), N);
    dfs(::maxNode, 0);    // 탐색한 정점에서 다시 가장 먼 정점 탐색

    cout << ::maxVal;
}