[그래프, 난이도 중] 프로그래머즈, 가장 먼 노드

노드 번호와, BFS의 깊이 변수를 가지는 구조체 node를 만들고 BFS를 수행했다.

큐에 담을 인접 노드가 하나도 없는 노드(이미 방문한 노드들 뿐)는 단일 노드라는 의미이므로, 이 노드는 가장 먼 노드의 후보가 된다.

아래 소스 코드에서 finished라는 bool 타입의 변수는, 큐에 담을 인접노드가 하나 이상 있는가의 여부를 판단한다.

 

가장 먼 노드의 후보로 꼽힌 노드들의 depth를 모아서 이들중 최댓값을 찾고, depth가 최댓값인 요소가 몇개 있는지 계산하면 문제가 해결된다.

 

테스트 케이스 9개 모두 통과

 

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node{
    int num;
    int depth;
};
queue<node> q;
vector<int> a[20001];
vector<int> depths;
bool visited[20001];

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    for(int i=0;i<edge.size();i++){
        a[edge[i][0]].push_back(edge[i][1]);
        a[edge[i][1]].push_back(edge[i][0]);
    }
    q.push({1,0});
    visited[1]=true;
    while(!q.empty()){
        node f=q.front();
        q.pop();
        bool finished=true;
        for(int i=0;i<a[f.num].size();i++){
            int y = a[f.num][i];
            if(!visited[y]){
                finished=false;
                visited[y]=true;
                q.push({y,f.depth+1});
            }
        }
        if(finished) depths.push_back(f.depth);
    }
    sort(depths.begin(),depths.end());
    int maxi = depths[depths.size()-1];
    for(int i=0;i<depths.size();i++){
        if(depths[i]==maxi) answer++;
    }
    return answer;
}