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

1167번: 트리의 지름

 

트리의 지름을 구하는 것은 생각보다 간단합니다.

트리의 특성상 양방향으로 연결된 노드들을 저장하게 되면, 어떤 노드든 루트 노드로 사용할 수 있습니다.

 

트리에서 일단 루트 노드에서 가장 멀리 떨어져 있는 노드를 찾고, 그 노드를 새로운 루트 노드로 삼습니다.

그 후, 새로운 루트에서 가장 멀리 떨어져 있는 노드를 찾고, 루트 노드와 가장 멀리 떨어져 있는 노드 사이의 거리를 구하면 이 거리가 트리의 지름이 됩니다.

가장 멀리 있는 노드를 찾을 때는 BFS 방식으로 탐색을 진행했습니다.

 

#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 V;
vector<vector<node> > tree;
vector<bool> isChecked;
vector<long long> distanceFromRoot;

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

  for (int i = 0; i < V; i++) {
    int vNum;
    cin >> vNum;

    int cvNum;
    int cvDist;
    while (cin >> cvNum && cvNum != -1) {
      cin >> cvDist;
      tree[vNum].push_back(node(cvNum, cvDist));
    }
  }
}

void initArray() {
  for (int i = 1; i <= V; 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 <= V; 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;
}