BFS 알고리즘 (+백준 1260번)

개념

너비 우선 탐색 (Breadth First Search), BFS 알고리즘은 맹목적 탐색 기법 중 하나이다.

맹목적 탐색 기법이란,
정해진 순서에 따라 상태 공간 그래프를 점진적으로 생성해가면서 해를 탐색하는 방법이다.

맹목적 탐색 기법에는 깊이 우선 탐색, 너비 우선 탐색, 반복적 깊이심화 탐색 등이 있으며
이 글에서는 너비 우선 탐색을 설명할 것이다.
(깊이 우선 탐색은 여기 -> https://velog.io/@fluid_silver/DFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

먼저 그림을 보자. (출처 : 학교 수업 pdf)

시작 정점으로부터 가까운 정점을 먼저 방문하고,
멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. (결국 다 방문함)
큐(queue)를 사용하여 구현한다.

알고리즘

1. 시작 정점을 큐에 저장
2. 큐의 맨 앞 정점의 이웃을 neighbor에 저장
3. 선택된 정점을 큐에서 제거
4. neighbor에 저장된 정점(+방문하지 않은 정점)들을 큐에 저장
5. 2~4 과정을 반복
6. 큐에 포함된 정점이 없을 때 알고리즘을 마침

코드

백준 1260번 DFS와 BFS : https://www.acmicpc.net/problem/1260

C++

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef struct Node Node;
struct Node {					// Node
    int data = 0;
    Node* next = NULL;
};
int main() {
	int N, M, V;
	cin >> N >> M >> V;
	vector<Node> head(N + 1);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		Node* tmp = new Node();	// linked list
		tmp->data = b;
		tmp->next = head[a].next;
		head[a].next = tmp;
		Node* tmp2 = new Node();
		tmp2->data = a;
		tmp2->next = head[b].next;
		head[b].next = tmp2;
	}
	queue<int> q;
	map<int, int> visited;		// 방문한 정점 저장
	q.push(V);
	cout << V << " ";
	visited.insert({ V, 1 });
	while (size(q) != 0) {		// 큐에 정점이 없을 때까지
		int curr = q.front();	// 큐의 맨 앞 정점
		Node head_tmp = head[curr];
		vector<int> neighbor;
		while (head_tmp.next != NULL) {	// 이웃 정점 저장
        	head_tmp = *head_tmp.next;
			neighbor.push_back(head_tmp.data);
		}
		q.pop();				// 선택된 정점 큐에서 제거
		sort(neighbor.begin(), neighbor.end());	// 번호가 작은 것 먼저 방문
		for (int i = 0; i < size(neighbor); i++) {
			if (visited.find(neighbor[i]) == visited.end()) {	// 방문하지 않은 정점
				q.push(neighbor[i]);		// 큐에 저장
				cout << neighbor[i] << " ";
				visited.insert({ neighbor[i], 1});
			}
		}
	}
	return 0;
}

Python

# 나중에 추가해보겠음

특징

BFS는 최단 경로 해의 탐색을 보장하지만
모든 이웃 정점을 방문하기 때문에 메모리 공간 사용이 비효율적이다.