[Programmers] 가장 먼 노드

그래프의 노드들에 대한 정보가 주어지고, 이 정보들을 활용하여 1에서 부터 가장 멀리 떨어진 노드들의 개수를 찾는 문제이다.

문제풀이 전략
노드 1로부터의 거리는 최단 거리라고 명시되어 있다.

최단거리는 bfs를 통해 구할 수 있다.

우선 그래프를 생성한다. vector를 활용하여 그래프를 생성해 주었다. 만약 배열을 사용하였다면 시간복잡도가 n^2이 되므로 시간초과가 날 것이다.

그리고 나서 bfs를 진행해 주는데, 방문 여부를 확인하기 위해 vector를 사용하였다.

방문 여부 백터를 1로 초기화 해준 후 bfs 과정에서 깊이를 저장해 준다.

깊이가 저장된 벡터를 정렬해서 가장 큰 값의 개수를 계산하면 된다.

코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> g(n+1);
    vector<int> visited(n+1,1);
    
    for(int i=0;i<edge.size();i++){
        int a = edge[i][0];
        int b = edge[i][1];
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    queue<pair<int,int>> q;
    q.push(make_pair(1,0));
    visited[1] = 0;
    
    while(!q.empty()){
        int h = q.front().first;
        int d = q.front().second;
        q.pop();
        
        for(int i=0;i<g[h].size();i++){
            if(visited[g[h][i]] != 1)
                continue;
            visited[g[h][i]] = -(d+1);
            q.push(make_pair(g[h][i],d+1));
        }
    }
    
    sort(visited.begin(), visited.end());
    
    for(int i=0;i<visited.size();i++){
        if(visited[0] == visited[i])
            answer++;
        else
            break;
    }
    
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/49189