[프로그래머스] 가장 먼 노드 [cpp]

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/49189
알고리즘 : bfs

핵심

1노드에서 가장 먼 거리를 구해야함.
간선을 전부 graph 큐에 삽입 후에
1번 노드부터 시작하여 방문하지 않은 노드에 대해서 대기열에 삽입
방문하지 않은 노드에 대해서는 현재노드의 간선 길이 + 1

#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> vertex) {
    // 그래프를 인접 리스트로 표현
    vector<vector<int>> graph(n + 1);
    // 각 노드에서 어디로 접근 가능한지 전부 기록
    for (auto edge : vertex) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }

    // 최단 거리 계산 (BFS)
    // 간선 기록
    vector<int> distance(n + 1, INT_MAX);
    queue<int> q;

    // 1번 노드에서 가장 긴 거리 측정
    distance[1] = 0; // 1번 노드에서 시작

    // 대기열에 삽입
    q.push(1);

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

        // 현재 노드에서 접근 가능한 노드 리스트
        for (int neighbor : graph[current]) {
            // 만약 노드가 이미 지나온 자리 (INT_MAX)가 아니라
            if (distance[neighbor] == INT_MAX) { // 방문하지 않은 노드만
                // 현재 노드까지 오는데 걸린 간선 거리에서 + 1
                distance[neighbor] = distance[current] + 1;
                // 방문하지 않은 노드들 대기열에 삽입
                q.push(neighbor);
            }
        }
    }

    // 가장 멀리 떨어진 노드 거리 계산
    int maxDistance = *max_element(distance.begin() + 1, distance.end());
    int count = count_if(distance.begin() + 1, distance.end(), [maxDistance](int d) { return d == maxDistance; });

    return count;
}