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

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/49189

풀이

---

1번 노드와 가장 먼 거리의 노드를 찾는 문제로, bfs를 통해 거리를 측정하고, 가장 큰 값을 가지는 원소의 개수를 리턴한다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> edge)
{
    int answer = 0;
    vector<vector<int>> arr(n + 1);
    vector<int> nodeDistance(n + 1, -1);

    for (int i = 0; i < edge.size(); i++)
    {
        arr[edge[i][0]].push_back(edge[i][1]);
        arr[edge[i][1]].push_back(edge[i][0]);
    }


    //Bfs
    queue<int> q;
    nodeDistance[1] = 0;
    q.push(1);

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

        for (int next : arr[cur])
        {
            if (nodeDistance[next] == -1)
            {
                nodeDistance[next] = nodeDistance[cur] + 1;
                q.push(next);
            }
        }
    }

    int farthest = *max_element(nodeDistance.begin(), nodeDistance.end());

    for (int i = 0; i < nodeDistance.size(); i++)
    {
        if (nodeDistance[i] == farthest)
        {
            answer++;
        }
    }

    return answer;
}