[c++/알고리즘] BFS 개념 및 예제

BFS (너비 우선 탐색)

• 개념:
  • BFS는 시작 노드에서부터 가까운 노드부터 차례대로 탐색하는 방식이다.
  • 주로 최단 경로를 찾는 문제나, 레벨 순서 탐색이 필요한 문제에서 유용하게 사용된다.
  • 너비 우선 탐색에서는 큐 (Queue) 자료 구조를 사용하여, 먼저 방문한 노드를 기준으로 탐색을 진행한다.
• 동작 원리:
  1. 초기화: 시작 노드를 큐에 넣고, 방문 표시를 한다.
  2. 큐에서 노드를 꺼내며 탐색: 큐에서 노드를 하나씩 꺼내며, 해당 노드와 인접한 노드를 모두 확인한다.
  3. 인접 노드를 큐에 추가: 방문하지 않은 인접 노드를 큐에 추가하고, 방문 표시를 한다.
  4. 반복: 큐가 빌 때까지 2번과 3번 과정을 반복한다.
• BFS 알고리즘의 특징:
  • 경로 길이 최적화: 가중치가 동일한 그래프에서 최단 거리를 찾을 수 있다.
  • 노드의 깊이 별 탐색: 깊이 레벨별로 탐색하기 때문에 같은 깊이에 있는 모든 노드를 탐색한 후에 다음 깊이로 넘어간다.

<코드 템플릿>

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

vector<int> graph[10];
bool isVisited[10] = { false };
void bfs(int start) {
	//BFS (너비 우선 탐색)
	queue <int> q;

	//초기화: 시작 노드를 큐에 넣고, 방문 표시
	q.push(start);
	isVisited[start] = true;

	//큐가 빌 때까지 과정 반복
	while (!q.empty()) {
		//가장 먼저 들어간 q값 추출 후 삭제
		int x = q.front();
		q.pop();
		cout << x << " " << endl;

		//아직 방문하지 않은 노드 탐색
		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];
			if (!isVisited[y]) {
				q.push(y);
				isVisited[y] = true;
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);

	// 노드 1에 연결된 노드 정보 저장
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[1].push_back(8);

	// 노드 2에 연결된 노드 정보 저장 
	graph[2].push_back(1);
	graph[2].push_back(7);

	// 노드 3에 연결된 노드 정보 저장 
	graph[3].push_back(1);
	graph[3].push_back(4);
	graph[3].push_back(5);

	// 노드 4에 연결된 노드 정보 저장 
	graph[4].push_back(3);
	graph[4].push_back(5);

	// 노드 5에 연결된 노드 정보 저장 
	graph[5].push_back(3);
	graph[5].push_back(4);

	// 노드 6에 연결된 노드 정보 저장 
	graph[6].push_back(7);

	// 노드 7에 연결된 노드 정보 저장 
	graph[7].push_back(2);
	graph[7].push_back(6);
	graph[7].push_back(8);

	// 노드 8에 연결된 노드 정보 저장 
	graph[8].push_back(1);
	graph[8].push_back(7);

	bfs(1);
}