[백준] 1167 트리의 지름 - C++

1. 문제 설명 

• 링크 : https://www.acmicpc.net/problem/1167

---

2. 풀이과정

• 문제 해결의 흐름 

1.  트리에서 임의의 두 점 사이의 거리에 대하여 가장 긴 거리를 찾는 문제이기에 임의의 두 점 사이의 거리를 모두 구해 가장 긴 거리를 찾는 방법을 떠올렸습니다. 즉, 완전탐색과 BFS를 결합하여 문제를 풀고자 하였습니다.
2.  하지만 아래와 같은 트리 구조를 예로 들어봤을 때, 굳이 완전탐색을 적용하여 모든 점을 탐색할 필요 없이 더 간단하게 풀 수 있는 방법이 있지 않을까 고민했습니다.

        1
       / \
      2   3
         / \
        4   5
             \
              6

 

   3. BFS는 특정 노드에서 출발하여 모든 노드를 거리 순으로 탐색하여, 각 노드까지의 최단 거리를 구할 수 있는데, 이 성질을 이용하여 단 2번의 BFS 를 수행하여 트리의 지름을 쉽게 찾을 수 있었습니다. 단, 이 문제는 간선 간의 가중치 또한 고려해주어야합니다! 

   4. 첫 번째 BFS를 수행하며 임의의 정점으로부터 가장 먼 노드를 찾습니다. 해당 노드는 트리 지름의 한 쪽 끝점이 됩니다.

   5. 이후 두 번째 BFS를 통해 앞서 찾은 노드에서 가장 먼 노드를 찾습니다. 이 과정에서 찾은 가장 먼 노드까지의 누적 거리가 바로 트리의 지름입니다.

  쉽게 이해하자면 트리의 정점을 인천, 서울, 대구, 부산, 제주도로 가정해봅시다. 서울, 대구, 부산 어느 곳에서 BFS를 시작하더라도 인천이나 제주도가 가장 먼 노드로 결정될 것입니다. 이후에 시작점을 인천으로 BFS를 수행하면 제주도로, 제주도로 BFS를 수행하면 인천으로 가장 먼 노드가 정해짐을 알 수 있습니다. 이를 통해 두 번째 BFS를 수행하며 트리의 지름을 구할 수 있습니다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int result = 0;

pair<int, int> bfs(int start, vector<vector<pair<int, int> > >& graph, int V) {
    vector<int> visited(V + 1, -1); // 거리 정보 저장하는데 사용하기
    queue<int> q;
    visited[start] = 0;
    q.push(start);
    int farthest_node = start; // 가장 먼 노드
    int max_dist = 0;

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

        for (pair<int, int> neighbor : graph[current]) { // neighbor : (정점 , 가중치)
            int next = neighbor.first;
            int weight = neighbor.second;

            if (visited[next] == -1) {
                visited[next] = visited[current] + weight; // 다음 노드까지의 거리 = 현재 노드까지의 거리 + 현재 노드에서 다음 노드로의 가중치
                q.push(next);
                // 새로 갱신된 거리가 기존 max_dist보다 크면 farthest_node를 갱신
                if (visited[next] > max_dist) {
                    max_dist = visited[next];
                    farthest_node = next;
                }
            }
        }
    }

    return make_pair(farthest_node, visited[farthest_node]);
}

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

    // 0. 입력 받기
    int V; // 정점의 개수 2 <= V <= 10만
    cin >> V;
    vector<vector<pair<int, int> > > graph(V + 1);
    for (int i = 0; i < V; ++i) {
        int v1; // 정점 번호
        cin >> v1;
        while (true) {
            int v2, d; // 정점 v1와 v2 간의 거리는 d이다.
            cin >> v2;
            if (v2 == -1) break;
            cin >> d;
            graph[v1].emplace_back(v2,d); // 트리 구조이기에 양방향 그래프
            graph[v2].emplace_back(v1, d);
        }
    }

    // 1. 트리의 지름 구하기 : bfs 2번 사용 (bfs는 거리 순으로 탐색하기에 마지막으로 탐색하는 노드가 가장 먼 노드임을 이용)
    pair<int,int> p1 = bfs(1,graph, V);
    pair<int, int> p2 = bfs(p1.first, graph, V);

    // 2. 출력하기
    cout << p2.second;

    return 0;
}

---

3. 후기

 BFS의 특성을 정확히 이해하여 문제 상황에 적용시켰다는 점이 정말 뿌듯합니다!