[프로그래머스/C++] 가장 먼 노드

프로그래머스

 

• 그래프에서 bfs/dfs 돌리면 되는 문제

 

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

using namespace std;

// 1번에서 가장 멀리 떨어진 노드가 몇 개인지 찾기. 가중치 X
// bfs/dfs 수행해서 가장 멀리 떨어진 노드까지의 거리를 저장하고 해당 거리랑 동일한 값을 갖는 노드를 카운트
// 우선 제공되는 간선 정보를 인접 리스트로 변환
// 이후 1번 노드부터 bfs 시작하며 각 노드에 최단 거리 저장

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> list(n + 1);
    
    // 인접 리스트로 변환
    for(int i = 0; i < edge.size(); i++) {
        list[edge[i][0]].push_back(edge[i][1]);
        list[edge[i][1]].push_back(edge[i][0]);
    }
    
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    // bfs 수행
    dist[1] = 0;
    q.push(1);
    
    while(!q.empty()) {
        int curNode = q.front();
        q.pop();
        
        for(int nextNode : list[curNode]) {
            if(dist[nextNode] == -1) {
                dist[nextNode] = dist[curNode] + 1;
                q.push(nextNode);
            }
        }
    }
    
    // 가장 큰 거리값 찾기
    int max = *max_element(dist.begin(), dist.end());
    
    // 가장 멀리 떨어진 노드들 찾기
    for(int i = 0; i < dist.size(); i++)
        // 거리가 가장 큰 거리값과 같으면
        if(dist[i] == max) answer++;
    
    return answer;
}