카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

bfs를 사용해서 시작 노드 1과 모든 노드 사이의 거리 정보를 distance에 저장

max 함수로 현재까지 탐색한 노드의 거리중 가장 먼 거리의 값을 max_dis에 저장

모든 노드 탐색 후 max_dis와 같은 값을 가진 distance의 요소 개수를 카운트하여 출력

int solution(int n, vector<vector<int>> edge) {
	int answer = 0;	
	queue<int> q;				// bfs 구현을 위한 큐
	vector<vector<int>> v(n+1);	// 간선 정보로 만든 그래프
	vector<int> visit(n + 1, 0);	// 해당 노드의 방문 여부 (1: 방문, 0: 미방문)
	vector<int> distance(n + 1, 0);	// 노드 1과 각 노드 i까지의 거리
    							// ex) distance[3] 은 1에서 3까지 거리: 1
                                        
	int max_dis=0;
	for (int i = 0; i < edge.size();i++) {
		v[edge[i][0]].push_back(edge[i][1]);
		v[edge[i][1]].push_back(edge[i][0]);
	}

	visit[1] = 1;
	q.push(1);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size();i++) {
			if (visit[v[x][i]] != 1) {
				distance[v[x][i]] = distance[x] + 1;
				visit[v[x][i]] = 1;
				q.push(v[x][i]);
				max_dis = max(max_dis, distance[v[x][i]]);
			}
		}
	}
	for (int i = 1; i <= n;i++) {
		if (max_dis == distance[i]) {
			answer++;
		}
	}

	return answer;
}