너비 우선 탐색(BFS) 응용 문제

문제는 BFS를 사용하여 가장 긴 경로를 찾는 것입니다.

임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 직경에 해당하는 노드 중 하나입니다.

백준 – 1167: 나무의 지름 결정

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

암호

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

typedef pair<int, int> p;
static vector <vector<p>> graph;
static vector <int> visited;
static vector <int> dist;
static queue<int> q;

void BFS(int i);

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, y, d, end;
    int max = 0;

    cin >> n;

    graph.resize(n + 1);
    visited.resize(n + 1, 0);
    dist.resize(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (true) {
            cin >> y;
            if (y == -1) {
                break;
            }
            cin >> d;
            graph(x).push_back(p(y, d));
        }
    }

    BFS(1); // 임의의 점에서 시작

    // 배열에서 가장 큰 거리 값을 가지는 노드를 시작점으로 지정
    for (int i = 2; i <= n; i++) {
        if (dist(i) > dist(max)) {
            max = i;
        }
    }

    fill(dist.begin(), dist.end(), 0); // 거리 배열 다시 초기화
    fill(visited.begin(), visited.end(), 0); // 방문 여부 다시 초기화

    BFS(max); // 가장 큰 거리값을 가진 노드를 시작점으로 지정
    sort(dist.begin(), dist.end()); // 오름차순
    cout << dist(n);

}

void BFS(int x) {
    queue <int> q;
    q.push(x);
    visited(x) = 1;

    while (!q.empty()) {
        int now_node = q.front();
        q.pop();
        for (p i: graph(now_node)) {
            if (visited(i.first) == 0) {
                visited(i.first) = true;
                q.push(i.first);
                // 거리 업데이트
                dist(i.first) = dist(now_node) + i.second;
            }
        }
    }
}