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

문제 링크

 

풀이

bfs를 이용하면 방문하는 노드가 최단거리가 됩니다. 거리를 기록하는 배열인 dist를 이용해 지금 노드에서 다음 노드를 방문할 때 +1을 해서 값을 갱신합니다.

 

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
    vector<vector<int>> vec(n + 1, vector<int>(n + 1));
    size_t size = edge.size();
    for (int i = 0; i < size; ++i)
    {
        auto n1 = edge[i][0];
        auto n2 = edge[i][1];
        vec[n1][n2] = 1;
        vec[n2][n1] = 1;
    }
    vector<bool> visited(n + 1, false);
    vector<int> dist(n + 1, 0);
    
    visited[1] = true;
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        auto node = q.front();
        q.pop();
        for (int i = 1; i <= n; ++i)
        {
            if (vec[node][i] == 1 && visited[i] == false)
            {
                visited[i] = true;
                q.push(i);
                dist[i] = dist[node] + 1;
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= n; ++i)
        max = max < dist[i] ? dist[i] : max;
    for (int i = 1; i <= n; ++i)
        if (max == dist[i])
            ++answer;
    return answer;
}