728x90
문제 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;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 1934번 - 최소공배수 (0) | 2024.07.10 |
---|---|
[C++] 백준 24445번 - 알고리즘 수업(너비 우선 탐색 2) (0) | 2024.07.09 |
[C++] 백준 24480번 - 알고리즘 수업(깊이 우선 탐색 2) (0) | 2024.07.05 |
[C++] 백준 24479번 - 알고리즘 수업(깊이 우선 탐색 1) (0) | 2024.07.04 |
[C++] 백준 10870번 - 피보나치 수 5 (0) | 2024.07.03 |