프로그래머스(C++) - 가장 먼 노드

●문제

 

●입출력

 

문제풀이

n의 갯수만큼의 graph가 존재하고 vertex 배열처럼 연결되어있을때 1번 노드에서 가장 멀리떨어진

노드의 갯수를 return

 

접근방법

bfs로 가장 먼 노드를 구하고 인접리스트로 구현

 

#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
int bfs(vector<vector<int>>& edge)
{
	queue<pair<int, int>> q;
	set<int> visited;

	//노드번호, 깊이
	q.push({ 1, 0 });
	visited.insert(1);

	map<int, int>count;
	while (!q.empty())
	{
		pair<int, int> current = q.front();
		q.pop();

		for (int i : edge[current.first])
		{
			int size = visited.size();
			visited.insert(i);
			//한번 방문한적이있다면 제외
			if (size == visited.size())
				continue;

			q.push({ i, current.second + 1 });
			count[current.second + 1]++;
		}
	}
	return count.rbegin()->second;


}
int solution(int n, vector<vector<int>> edge)
{
	//인접리스트
	vector<vector<int>> graph(n + 1);
	
	for (auto& e : edge)
	{
		int a = e[0];
		int b = e[1];

		//양방향 그래프
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	return bfs(graph);

}

 

레벨 : 3

점수 : 1