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

1967번: 트리의 지름

 

 

이전에 풀었던 1167번 문제와 아주 유사합니다.

 

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

 

 

저는 1167번 문제에서 input 함수 내용만 조금 바꿨습니다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct node {
  int num;
  int dist;

  node(int num, int dist) : num(num), dist(dist) {};
};

int N;
vector<vector<node> > tree;
vector<bool> isChecked;
vector<long long> distanceFromRoot;

void input() {
  cin >> N;
  tree.resize(N + 1);
  isChecked.resize(N + 1);
  distanceFromRoot.resize(N + 1);

  for (int i = 0; i < N - 1; i++) {
    int vNum;
    cin >> vNum;

    int cvNum;
    int cvDist;
    cin >> cvNum >> cvDist;
    tree[vNum].push_back(node(cvNum, cvDist));
    tree[cvNum].push_back(node(vNum, cvDist));
  }
}

void initArray() {
  for (int i = 1; i <= N; i++) {
    isChecked[i] = false;
    distanceFromRoot[i] = -1;
  }
}

void bfs(int root) {
  initArray();

  queue<int> q;
  q.push(root);
  isChecked[root] = true;
  distanceFromRoot[root] = 0;

  while (!q.empty()) {
    int x = q.front();
    q.pop();

    for (node n : tree[x]) {
      int nx = n.num;
      int dist = n.dist;

      if (!isChecked[nx]) {
        isChecked[nx] = true;
        distanceFromRoot[nx] = distanceFromRoot[x] + dist;
        q.push(nx);
      }
    }
  }
}

int findNewRootNode(int root) {
  int newRoot = -1;
  long long dist = -1;
  bfs(root);

  for (int i = 1; i <= N; i++) {
    if (dist == -1 || dist < distanceFromRoot[i]) {
      dist = distanceFromRoot[i];
      newRoot = i;
    }
  }
  return newRoot;
}

void printAnswer(int farthestNode) {
  cout << distanceFromRoot[farthestNode] << '\n';
}

int main() {
  ios::sync_with_stdio(false);

  input();
  int newRoot = findNewRootNode(1);
  int farthestNode = findNewRootNode(newRoot);
  printAnswer(farthestNode);

  return 0;
}