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

#접근방법 

 

먼저 그래프의 정보를 다 담아놓자 

양방향 간선이기 때문에 from 에서 to로 그리고 to 에서 from 의 정보를 저장한다. 

 

이차원 벡터에서 인덱스 3번에 4, 8 ,9 가 붙어있따면 

 

노드 3에서 노드 4,

노드 3에서 노드 8,

노드 3에서 노드 9 

 

로 연결되어 있다는 뜻! 

 

이후 bfs() 를 적용하기 위해서는 queue 를 생성하는데 처음 담아지는 원소의 값은 1이다 

 

왜냐하면 1에서 가장 멀리 떨어지는 노드를 찾는거니까 1이 시작점인거지!

 

그리고 queue가 빌때 동안 queue의 첫번째 값을 꺼집어내서 그 값에 연결되어 있는 값들을 

queue에 다시 붙여준다. 

 

근데 이때 거리도 하나 올려서 거리 배열에 기록해주자. 

 

근데 만약 현재 보고있는 노드번호에 거리 배열을 찾아가보니까 값이 이미 있다? 그러면 이전에 방문했던 적이 있다는 뜻이다. 그러므로 해당 값이 존재한다면 그냥 무시하자

 

이후 dist배열이 모두 세팅되면 해당 배열에서 가장 큰 값을 가지는 원소의 개수를 세어주면 이 문제는 풀린다!

 

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

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int from, to; 
    vector <vector<int>> graph(n+1); 
    vector <int> dist(n+1, -1); 
    for(int i=0; i<edge.size(); i++){
        from = edge[i][0]; 
        to = edge[i][1]; 
        graph[from].push_back(to);     
        graph[to].push_back(from); 
    }
    queue<int> q; 
    q.push(1); 
    dist[1]=0; 
    while(!q.empty()){
        int current = q.front(); 
        q.pop(); 
        int d = dist[current]; 
        for(int i=0; i<graph[current].size(); i++){
            int next = graph[current][i]; 
            if(dist[next]!=-1)continue; 
            dist[next] = d+1;      
            q.push(next); 
        }
    }
    sort(dist.begin(), dist.end(), greater<int>()); 
    int pos = 0; 
    while(dist[pos++]==dist[0]){
        answer++; 
    }
    return answer;
}

 

코딩테스트 연습 - 가장 먼 노드