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

programmers.co.kr/learn/courses/30/lessons/49189

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

1번 노드로부터 최단 거리 중 가장 먼 노드들의 개수를 찾는 것이다.

 

즉, 1번으로부터 4번 5번 6번 노드의 최단 거리가 3이고 그 거리가 그래프에서 1번과 가장 먼 거리면 정답은 3이다.

 

따라서 나는 input을 인접 리스트에 저장하고, BFS를 수행해서 최단거리를 찾으면 되겠다고 생각했다.

 

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

using namespace std;

vector<int> v[20001];
int check[20001], record[20001], mn;

void BFS(int startx){
    queue<int> q;
    check[startx] = true;
    q.push(startx);
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        
        for(int i = 0;  i < v[x].size() ; i++){
            int next = v[x][i];
            if(!check[next]){
                q.push(next);
                check[next] = true;
                record[next] = record[x] + 1;
                mn = max(mn, record[next]);
            }
        }
    }
    
    
}


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);
    }
    
    BFS(1);
    
    for(int i = 1 ; i <= n ; i++){
        if(record[i] == mn)
            answer++;
    }
    
    
    return answer;
}

BFS를 진행하면서 모든 경로에 1번과의 거리를 저장해준다.

 

이후 계산해두었던 최장거리를 노드들의 거리와 비교하면서 그 거리에 해당하는 노드면 개수를 세줬다.

 

인접 리스트 구현으로 BFS의 시간 복잡도는 O(V+E)로 충분했다.