경주장

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

코테/프로그래머스

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

달리는치타 2021. 3. 16. 23:41
#include <queue>
#include <vector>
#include <iostream>


#define INF 500001
#define MAX(x,y) x>y?x:y


using namespace std;

vector<int> a[20001]; //edge info
int cost[20001];

void dijkstra(int s)
{
    cost[s] = 0;
    queue<pair<int,int>> pq;
    pq.push({s,0});

    while(!pq.empty())
    {
        int cur = pq.front().first;
        int dist = -pq.front().second;
        pq.pop();

        if(cost[cur] < dist) continue;
        for(int i = 0 ; i < a[cur].size(); i++)
        {
            int next = a[cur][i];
            int nextDist = dist + 1;
            if(nextDist < cost[next])
                {
                    cost[next] = nextDist;
                    pq.push({next,-nextDist});
                }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
   for(auto e : edge)
   {
       a[e[0]].push_back(e[1]);
       a[e[1]].push_back(e[0]);
   }

   for(int i = 1; i <= n ; i ++)
        cost[i] = INF;

    dijkstra(1);

    int count = 0 ; 
    int cur_max = 0;

    for(int i = 1; i <= n ; i++)
        {
           if(cur_max == cost[i])
            {
                count++;
            }
            else{
                cur_max = cost[i];
                count = 1;
            }    
                        
        }
    return count;
}

int main()
{
    int n = 6;
    vector<vector<int>> edge = {{3,6},
                                {4,3},
                                {3,2},
                                {1,3},
                                {1,2},
                                {2,4},
                                {5,2}};
    cout<<solution(n, edge);
}

 

'코테 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 순위  (0) 2021.03.14
[프로그래머스] 입국심사  (0) 2021.03.09