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

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

문제 링크

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector <int> v[20001];
queue <pair<int, int>> q;
int visit[20001];
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for(int i=0; i<edge.size(); i++){
        int from = edge[i][0];
        int to = edge[i][1];
        
        v[from].push_back(to);
        v[to].push_back(from);
    }
    
    q.push({1, 0});
    visit[1] = 1;
    int max_distance = 0;
    
    while(!q.empty()){
        int vertex = q.front().first;
        int distance = q.front().second;
        q.pop();
        
        for(int i=0; i<v[vertex].size(); i++){
            if(!visit[v[vertex][i]]){
                visit[v[vertex][i]] = distance + 1;
                q.push({v[vertex][i], distance + 1});            
	            max_distance = max(max_distance, distance + 1);
            }   
        }
    }
    
    
    for(int i=1; i<=n; i++){
    	if(visit[i] == max_distance) answer++;
    }
    
    return answer;
}

• 그래프 구현 문제
• 연결 리스트 형식으로 그래프 구현 후, 노드의 갯수만큼 돌면서 방문 처리를 해 준다.
• 가장 먼 거리를 업데이트 해가면서 노드를 전부 방문한다.
• visit 배열이 가장 먼 거리와 일치하는 것의 갯수를 센다.