경주장
[프로그래머스] 가장 먼 노드 본문
#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 |