가장 먼 노드 [Lv. 3]

프로그래머스

 

N개의 노드가 있는 그래프에서 

1번 노드에서부터 가장 먼 노드가 몇개 있는지 찾는 문제입니다.

 

풀이 방법

하나의 노드에서 모든 노드로부터의 최단 경로를 찾는 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있습니다.

for(auto& e : edge){
    v[e[0]].push_back(e[1]);
    v[e[1]].push_back(e[0]);
}

입력받은 모든 간선을 양방향 그래프로 만들어주고

 

void dijkstra()
{
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    dist[1] = 0;
    dist[0] = -1;
    
    while (q.size())
    {
        auto [cost, node] = q.top(); q.pop();
        cost *= -1;
        
        for (int nxt : v[node])
        {
            if (dist[nxt] > cost + 1)
            {
                dist[nxt] = cost + 1;
                q.push({-(cost+1), nxt});
            }
        }
    }
}

거리를 비교하는 방식으로 최단 거리를 구해줍니다.

 

int maxDist= 0;
int cnt = 0;
for (int d : dist)
    maxDist = max(maxDist, d);

for (int d : dist)
    if (d == maxDist)
        cnt++;

return cnt;

이 후 거리를 순회하여 가장 먼 거리를 찾고

해당 거리를 가진 노드의 수를 찾아 출력해주면 해결됩니다.