가장 먼 노드

코드

[ 다익스트라 ] - 시간초과

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e9
//12:06
// 다익스트라 O(NlogN) 
// 이 문제는 O(N^2)는 불가능함 약 4억개의 연산을 처리해야 하기 때문
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();
        // i는 의미가 없음
        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]); // 양방향
    }
    /* BFS */
    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개의 좌표에 대해 수행하기 때문