[백준 - 24445] 너비 우선 탐색 2

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

#define MAX 100'005
#define FRONT q.front()

vector<int> nodes[MAX];
bool isVisit[MAX];
int result[MAX];

queue<int> q;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N, M, R; cin >> N >> M >> R;

	int temp1, temp2;
	for (int i = 0; i < M; ++i)
	{
		cin >> temp1 >> temp2;
		nodes[temp1].push_back(temp2);
		nodes[temp2].push_back(temp1);
	}

	//내림차순 정렬하기
	for (int i = 1; i <= N; ++i)
	{
		sort(nodes[i].begin(), nodes[i].end(),greater<>());
	}

	q.push(R);
	memset(isVisit, 0, sizeof(bool) * MAX);
	isVisit[R] = true;
	memset(result, 0, sizeof(int) * MAX);
	result[R] = 1;
	int cnt = 1;
	while (q.empty() == false)
	{
		for (const auto & data : nodes[FRONT])
		{
			if (isVisit[data] == false)
			{
				q.push(data);
				isVisit[data] = true;
				result[data] = ++cnt;
			}
		}
		q.pop();
	}

	for (int i = 1; i <= N; ++i)
	{
		cout << result[i] << "\n";
	}
	return 0;
}

---

||사고 과정

단순 BFS를 구현하는것이기에 특별한 사고는 없었다.

---

||사용 기법

• BFS

---

||풀면서 느낀 것

• 노드를 1부터 시작하면 주의할것

이번에 이것때문에 30분정도 시간을 소모했는데 BFS는 노드의 인덱스가 1부터 N까지 탐색하지만

입력 받을 때 0부터 N-1 까지 탐색하고 있었다 =~=

이건 종종 있는 일이라 주의할 겸 포스팅을 했다.

---

||나아 진것

• 좀 더 수월한 BFS

역시 계속 다루다 보니까 계속 더 빠르게 구현이 되는듯하다.