[C++] 백준 24444번 - 알고리즘 수업(너비 우선 탐색 1)

 

 

문제 24444번

https://www.acmicpc.net/problem/24444

 

 

이번에는 너비 우선 탐색이다. 깊이 우선 탐색과는 bfs() 함수가 있는 부분만 다르다. 먼저 큐를 만들어 해당 정점을 넣어주고 방문처리를 한다. cnt를 하나 증가시킨 후 결과 배열에 넣어준다.

 

큐의 맨 앞 요소를 변수에 저장한 후 pop으로 빼준다. 그리고 해당 요소를 인덱스로 하여 그것과 이어져있는 점들의 크기만큼 반복해준다. 만약 방문한 점이라면 cnt를 1증가시키고 result 배열에 넣어준다. 그리고 넣어준 인덱스를 큐에 삽입하고 방문처리를 한다. 이 과정을 큐가 빌때까지 계속 반복해준다.

 

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

vector<int> graph[100001];
int visited[100001];
int result[100001];
int cnt = 0;

void bfs(int r) {
	queue<int> q;
	q.push(r);
	visited[r] = true;
	cnt++;
	result[r] = cnt;
	while (!q.empty()) {
		int first = q.front();
		q.pop();
		for (int i = 0; i < graph[first].size(); i++) {
			int temp = graph[first][i];
			if (!visited[temp]) {
				cnt++;
				result[temp] = cnt;
				q.push(temp);
				visited[temp] = true;
			}
		}
	}
}

int main() {
	int n, m, r;
	cin >> n >> m >> r;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {	//오름차순
		sort(graph[i].begin(), graph[i].end());
	}
	bfs(r);
	for (int i = 1; i <= n; i++) {
		cout << result[i] << '\n';
	}
	return 0;
}