[백준 24444] 알고리즘 수업 - 너비 우선 탐색 1

최근에 DFS 백트래킹만 풀어서 BFS 복습하려고 품

 

visited 배열을 bool로 하는 것보다 bitset<SIZE>로 하는게 훨씬 공간복잡도와 시간복잡도 측면에서 좋다.

bitset도 direct memory access가 가능한 자료구조라 쓸 가치가 있다.

 

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <bitset>
#define SIZE 100001

using namespace std;

int N, M, R;
vector<int> arr[SIZE];
int ans[SIZE];
bitset<SIZE> visited;

void BFS(int R) {
	// 초기설정
	visited.set(0);
	int cnt = 1;
	
	queue<int> q;
	visited[R] = 1;
	q.push(R);
	ans[R] = cnt++;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int i = 0; i < arr[cur].size(); i++) {
			int node = arr[cur][i];
			if (!visited[node]) {
				visited[node] = 1;
				q.push(node);
				ans[node] = cnt++;
			}
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> R;
	int u, v;
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		arr[u].push_back(v);
		arr[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) sort(arr[i].begin(), arr[i].end());

	BFS(R);

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