[ 그래프 이론 - 24444 ] 알고리즘 수업 - 너비 우선 탐색 1

---

접근법

Sudo Code 기반으로 작성하면 쉽게 해결 가능하다.

sort()를 이용해서 정렬을 통해 정점 번호를 오름차순으로 방문 하였지만, 추후 다른 정렬 기법 기반으로 정렬을 구현할 필요는 보인다.

---

정답

#include<iostream>
#include<queue>
#include<vector>
#include <algorithm>
using namespace std;

vector<int32_t> ars32_Graph[100001];
bool arb_Visited[100001] = { false };
int32_t ars32_Result[100001];

void bfs(int32_t s32_R);

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int32_t s32_N, s32_M, s32_R, s32_I;
	cin >> s32_N >> s32_M >> s32_R;

	for (s32_I = 1; s32_I <= s32_M; s32_I++)
	{
		int32_t s32_Tmp1, s32_Tmp2;
		cin >> s32_Tmp1 >> s32_Tmp2;
		ars32_Graph[s32_Tmp1].push_back(s32_Tmp2);
		ars32_Graph[s32_Tmp2].push_back(s32_Tmp1);
	}

	for (s32_I = 1; s32_I <= s32_N; s32_I++)
	{
		sort(ars32_Graph[s32_I].begin(), ars32_Graph[s32_I].end());
	}


	bfs(s32_R);

	for (s32_I = 1; s32_I <= s32_N; s32_I++)
	{
		printf("%d\n", ars32_Result[s32_I]);
	}

	return 0;
}

void bfs(int32_t s32_R)
{
	int32_t s32_I, s32_Cnt=1;
	
	queue<int32_t> qs32_Queue;
	qs32_Queue.push(s32_R);
	ars32_Result[s32_R] = s32_Cnt;
	arb_Visited[s32_R] = true;

	while (!qs32_Queue.empty())
	{
		int32_t s32_Node = qs32_Queue.front();

		qs32_Queue.pop();

		for (s32_I = 0; s32_I < ars32_Graph[s32_Node].size(); s32_I++)
		{
			if (!arb_Visited[ars32_Graph[s32_Node][s32_I]])
			{
				s32_Cnt += 1;
				ars32_Result[ars32_Graph[s32_Node][s32_I]] = s32_Cnt;
				arb_Visited[ars32_Graph[s32_Node][s32_I]] = true;
				qs32_Queue.push(ars32_Graph[s32_Node][s32_I]);
			}
		}

	}
	
}