[프로그래머스] (Graph) 가장 먼 노드 [C++]

👉 문제 확인 (프로그래머스 - 가장 먼 노드 ) 👈

🤍 접근

처음에는 dfs로 접근하였는데 위의 예시에서 1, 3, 2 와 같은 경우에서
1과 2 사이의 거리는 1인데 1->3->2와 같이 측정되어 거리가 2로 인식되는 오류가 생겼다. 그래서 bfs로 다시 접근하여보았다.

완성 코드

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

using namespace std;

//bfs => 최단경로 ,미로찾기 같은거 <= queue 이용

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> graph(n+1);
    vector<bool> visited(n+1,false);
    queue<int> q;
    vector<int> distance(n +1 , 0);
    
    for(vector<int> e : edge){
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    q.push(1);
    visited[1] = true;
    
    while(!q.empty()){
        int start = q.front();
        q.pop();
        
        for(int i = 0; i < graph[start].size() ; i++){
            int end = graph[start][i];
            if(!visited[end]){
                visited[end] = true;
                distance[end] = distance[start] + 1;
                q.push(end);
            }
        }
    }
    
    sort(distance.rbegin(), distance.rend()); // 내림차순
    for(int d : distance){
        if(d == distance[0]) answer++;
        else break;
    }
   
    return answer;
}