그래프의 노드들에 대한 정보가 주어지고, 이 정보들을 활용하여 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