백준 5567 c++

2024년 2월 21일

BFS를 활용해 시작위치로부터 일정 거리 내에 있는 값까지만 고려해 결과를 도출한다.
BFS를 수행하는 과정에서 for문을 다른 풀이보다 하나 더 사용해 비효율성이 발생한 것 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;
vector <vector<int>> graph;
vector <bool> visited;

void input_graph()
{
	int i;
	int a, b;

	graph.resize(n + 2);
	visited.resize(n + 2, false);
	for (i = 0; i < m; i++)
	{
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	//그래프 확인
	/*for (i = 0; i <= n; i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}*/

	return;
}

int BFS(int start)
{
	int i, j;
	int count = 0;
	int friend_relation = 1;
	int current, next, size, q_size;
	queue <int> q;

	q.push(start);
	visited[start] = true;
	while (!q.empty())
	{
		q_size = q.size();
		for (i = 0; i < q_size; i++)
		{
			current = q.front();
			q.pop();
			size = graph[current].size();
			for (j = 0; j < size; j++)
			{
				next = graph[current][j];
				if (visited[next] == false)
				{
					q.push(next);
					visited[next] = true;
					count++;
				}
			}
		}
		friend_relation++;
		if (friend_relation == 3)
		{
			break;
		}
	}

	return count;
}

int find_answer()
{
	return BFS(1);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	input_graph();
	cout << find_answer() << "\n";

	return 0;
}