[ 다익스트라 ] - 시간초과
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e9
using namespace std;
vector<pair<int,int>> graph[20001];
int dis[20001];
void Dijkstra(int start){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
dis[start] = 0;
while(!pq.empty())
{
int dist = pq.top().first;
int now = pq.top().second;
if(dis[now] < dist) continue;
pq.pop();
for(int i=0;i<graph[now].size();i++)
{
int cost = dis[now] + graph[now][i].second;
if(dis[graph[now][i].first] < cost) continue;
dis[graph[now][i].first] = cost;
pq.push({cost, graph[now][i].first});
}
}
}
int solution(int n, vector<vector<int>> edge) {
int answer = 0;
fill(dis, dis+20001, INF);
for(int i=0;i<edge.size();i++)
{
graph[edge[i][0]].push_back({edge[i][1], 1});
graph[edge[i][1]].push_back({edge[i][0], 1});
}
Dijkstra(1);
int Max=0;
for(int i=2;i<=n;i++)
if(dis[i] != INF) Max=max(Max,dis[i]);
for(int i=2;i<=n;i++)
if(dis[i] != INF and dis[i] == Max) answer++;
return answer;
}
- 로직
: 다익스트라
를 활용해서 1번 노드
에서 모든 노드
까지 거리를 구한 후 최대 개수
구함
- 결과
시간초과
- 해당 문제의
시간 복잡도
는 O(NlogN)
이다
- 이 문제는 굳이
다익스트라
를 쓰지 않아도 BFS
를 하면 O(N)
이 가능함
[ BFS풀이 ]
#include <string>
#include <vector>
#include <queue>
using namespace std;
int cost[20001];
vector<int> v[20001];
int solution(int n, vector<vector<int>> edge) {
int answer = 0;
for(int i=0;i<edge.size();i++)
{
v[edge[i][0]].push_back(edge[i][1]);
v[edge[i][1]].push_back(edge[i][0]);
}
queue<int> q;
q.push(1);
cost[1] = 1;
int MAX=0;
while(!q.empty())
{
int cur = q.front(); q.pop();
for(int i=0;i<v[cur].size();i++)
{
int nx = v[cur][i];
if(cost[nx] != 0) continue;
q.push(nx);
cost[nx] = cost[cur] + 1;
MAX = max(MAX, cost[nx]);
}
}
for(int i=2;i<=n;i++)
if(cost[i] == MAX) answer++;
return answer;
}
- 로직
: BFS
를 써서 연결된 모든 정점
까지 최단거리
를 구하고 개수를 셈
- 시간 복잡도
O(N)
: 한 정점
에서 최대 N개
의 좌표에 대해 수행하기 때문