<프로그래머스> Level3 가장 먼 노드

가장 먼 노드

문제

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

노드의 개수 n은 2 이상 20,000 이하입니다.

간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.

vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n vertex                                              return

6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

문제 풀이

BFS를 활용하여 문제를 풀었다.

문제는 1이라는 노드에서 시작해서 가장 먼 노드들의 갯수를 return 하면 된다. 이때 가장 먼 노드란 최단 경로를 기준으로 한다. 따라서 BFS를 통해서 각 노드에 접근하면서 최단 거리를 min_dis 벡터에 저장한다. 이후 min_dis를 역순으로 정렬한 뒤, 가장 앞에 있는 값이 가장 먼 노드가 되며 앞에서 부터 max값과 다른 값이 나올때까지 세면 가장 먼 노드들의 갯수를 구할 수 있다.

C++ 코드

#include <vector>
#include <queue>
#include <utility>          //pair
#include <functional>       //greater
#include <algorithm>        //sort
 
using namespace std;
 
bool DescendingOrder(const int a, const int b){
    return a>b;
}
 
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<int> min_dis(n,0);
    vector<bool> visited(n,false);
    vector<vector<bool>> graph(n,vector<bool>(n,false));
    for(auto vertex : edge){
        graph[vertex[0]-1][vertex[1]-1] = true;
        graph[vertex[1]-1][vertex[0]-1] = true;
    }
  
    queue<pair<int,int>> q;
    for(int i=0; i<n;i++){      //1번 노드의 연결된 노드들을 큐안에 넣음(초기값 넣어주기)
        if(graph[0][i])
        {
            q.push(make_pair(i,1));     //pair (node, cnt)
            visited[0] = true;
            visited[i] = true;
            min_dis[i] = 1;
        }
    }
    
    while(!q.empty()){      //BFS
        pair<int,int> temp = q.front();
        q.pop();
        for(int i=0;i<n;i++){
            if(graph[temp.first][i]&&!visited[i]){
                visited[i]=true;
                min_dis[i]=1+temp.second;
                q.push(make_pair(i,min_dis[i]));
            }
        }
    }
    
    sort(min_dis.begin(), min_dis.end(),DescendingOrder);
    //sort(min_dis.begin(), min_dis.end(),greater<int>);    #<functional>
    int max = min_dis.front();
    for(auto a : min_dis){
        if(a==max){
            answer++;
        }else{
            break;
        }
    }
   
    return answer;
}

문제를 1 차적으로 풀고 개선점을 생각해 보았다. 

1. min_dis에 거리를 저장해 놓기 때문에 pair형태로 큐를 만들 필요가 없다. 큐에는 노드만 넣고 거리는 min_dis에서 가져오자
2. sort 함수의 시간 복잡도는 O(nlogn)이고  BFS 도중 max값을 구한 다음 min_dis에서 max와 같은 값을 찾는다고 하면 O(n)이므로 sort 함수를 사용하는 것이 좀 더 효율적이다. 이건 잘 한거 같다.

문제 출처 :https://programmers.co.kr/learn/courses/30/lessons/49189