문제 푼 날짜 : 2021-08-16

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49189

접근 및 풀이

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 알아야 했으므로 Dijkstra 알고리즘을 떠올렸다.
전형적인 Dijkstra 알고리즘을 구현하였고, max_element 함수와 lower_bound를 이용하여 가장 멀리 떨어진 노드의 갯수를 구해주었다.

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 987654321

vector<pair<int, int>> v[20001];

vector<int> dijkstra(int start, int n) {
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push(make_pair(0, start));
    
    while (!pq.empty()) {
        int now = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        
        if (dist[now] < cost) {
            continue;
        }
        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i].first;
            int nCost = cost + v[now][i].second;
            
            if (dist[next] > nCost) {
                dist[next] = nCost;
                pq.push(make_pair(nCost, next));
            }
        }
    }
    return dist;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for (auto e : edge) {
        v[e[0]].push_back(make_pair(e[1], 1));
        v[e[1]].push_back(make_pair(e[0], 1));
    }
    vector<int> ret = dijkstra(1, n);
    
    for (int i = 0; i <= n; i++) {
        if (ret[i] == INF) {
            ret[i] = -1;
        }
    }
    sort(ret.begin(), ret.end());
    int maxNum = *max_element(ret.begin(), ret.end());
    answer = ret.end() - lower_bound(ret.begin(), ret.end(), maxNum);
    
    return answer;
}

결과

피드백

Dijkstra 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제였다.