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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

1번 노드로 부터 각 노드까지의 최단 거리를 구한 후, 최단 거리가 최대인 노드의 개수를 구하는 문제이다.

1번 노드를 출발지점으로 하여 bfs를 수행시키고, 각 노드를 방문할 때 최단 거리를 기록한다.

1번 노드로 부터 x번 노드까지의 최단 거리를 dist[x]라 할 때, dist[x] 값 중 최댓값을 구하고, 최댓값을 갖는 x의 개수를 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

void setGraph(vector<vector<int>>& graph, const vector<vector<int>> edge) {
    
    for (auto v : edge) {
        int a = v[0];
        int b = v[1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void bfs(vector<int>& dist, const vector<vector<int>> graph) {
    
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    
    while (!q.empty()) {
        
        int cur = q.front();
        q.pop();

        for (auto x : graph[cur]) {
            if (dist[x] != -1) continue;
            dist[x] = dist[cur]+1;
            q.push(x);
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    
    vector<vector<int>> graph(n+1, vector<int>(0));
    setGraph(graph, edge);
    
    vector<int> dist(n+1, -1);
    bfs(dist, graph);
    
    int cnt = 0;
    int mx = *max_element(dist.begin(), dist.end());
    for(auto x : dist) 
        if (x == mx) cnt++;
    return cnt;
}