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

BFS를 이용해 가장 긴 경로를 찾는 문제이다. 

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

 

백준 - 1167: 트리의 지름 구하기

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

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;
            }
        }
    }
}

 

나의 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#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;
    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[max] < dist[i]) {
            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) {

    visited[x] = 1;
    int a;

    for (p i : graph[x]) {
        if(visited[i.first] == 0){
            visited[i.first] = 1;
            q.push(i.first);
            dist[i.first] = dist[x] + i.second;
        }
        else {
            continue;
        }
    }

    if (q.size() == 0) {
        return;
    }

    a = q.front();
    q.pop();
    BFS(a);

}