반응형
풀이 일시 : 2020-08-30
BFS :
탐색 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것. 그 중 한 방법인 너비우선탐색은 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문한다.
DFS와 비교하여 wide 하게 탐색하는 BFS는 queue를 이용하여 구현할 수 있다.
최단거리를 구할때 주로 이용된다.
문제 :
BFS를 queue로 구현하라.
풀이 :
인접 노드들을 queue에 담고 그 다음 노드는 큐에서 나오는 노드가 될 것이다. 그 노드의 인접노드를 다시 queue에 넣는 작업을 queue가 비기 전 까지 반복해준다.
#include <iostream>
#include <queue>
#include <vector>
#define MAX 101
using namespace std;
vector <int> a[MAX];
int d[MAX] = { 0, };
void bfs(int x) {
queue <int> q;
q.push(x);
d[x] = true;
while (!q.empty()) {
int y = q.front();
q.pop();
printf("%d", y);
for (int i = 0; i < a[y].size(); i++) {
int z = a[y][i];
if (!d[z]) {
q.push(z);
d[z] = true;
}
}
}
}
int main() {
a[1].push_back(2);
a[2].push_back(1);
a[1].push_back(3);
a[3].push_back(1);
a[1].push_back(8);
a[8].push_back(1);
a[2].push_back(7);
a[7].push_back(2);
a[7].push_back(6);
a[6].push_back(7);
a[7].push_back(8);
a[8].push_back(7);
a[3].push_back(4);
a[4].push_back(3);
a[3].push_back(5);
a[5].push_back(3);
a[4].push_back(5);
a[5].push_back(4);
bfs(1);
return 0;
}
추가자료 : [개념정리] 큐 (queue)
dbstndi6316.tistory.com/48?category=953968
dbstndi6316.tistory.com/27?category=953970
반응형
'알고리즘 문제풀이 > 기본문제풀이' 카테고리의 다른 글
[기본문제풀이] 분할정복 (0) | 2020.12.29 |
---|---|
[기본문제풀이] DFS 깊이우선탐색 (0) | 2020.12.29 |
[기본문제풀이] greedy 알고리즘 (0) | 2020.12.29 |
[기본문제풀이] rabin karp 알고리즘 (0) | 2020.12.28 |
[기본문제풀이] KMP알고리즘 (0) | 2020.12.28 |
댓글