BFS

BFS(Breadth First Search)

• 그래프 순회 방법 중 하나(너비 우선 탐색)
• 시작 노드에서 인접노드를 방문하고, 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복한다.

Queue(큐)를 이용한 BFS 풀이

입력 5(노드의 수) 6(간선의 수)

0 1 0 2 1 3 1 4 2 4 3 4 (간선이 존재하는 노드의 쌍 입력)

출력

0 1 2 3 4

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define max 10
int n, e;
int graph[max][max];
void bfs(int node){
	bool visited[max]= {false};
	
	queue<int>myqueue;
	visited[node]=true;
	myqueue.push(node);
	
	while(!myqueue.empty()){
		int curr = myqueue.front();
		myqueue.pop();
	
	cout<<curr<<' ';
	for(int next = 0; next<n;++next){
		if(!visited[next] && graph[curr][next]){
			visited[next] = true;
			myqueue.push(next);	
		}
	}
	}
}
int main()
{
	cin>>n>>e;
	memset(graph,0,sizeof(graph));
	for(int i=0;i<e;i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u][v]=graph[v][u]=1;
	}
	bfs(0);
	return 0;
}

다음 코드를 통해 방문한 노드를 기준으로 인접 노드를 방문할 수 있는 방법이 생긴다 

큐의 선입선출 구조를 활용한 것이다.

bfs 활용 - Shortest path algorithm

입력

5 

0 0 0 0 0

0 1 1 1 1

0 0 0 0 0

1 1 1 1 0

0 0 0 0 0

0은 빈공간 1은 벽을 의미 (시작점에서 도착점 까지 가는 최단거리 구하기)

0 1(시작점) 4 2(도착점)

출력

11

<코드>

#include <iostream>
#include <queue>
#define max 10
using namespace std;
int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 상하좌우 이동
int Board[max][max];
int n;
struct Point{
	int row, col, dist;
};

int bfs(int srcRow, int srcCol, int dstRow, int dstCol){
	bool visited[max][max] = {false}; // 재귀호출을 하지 않으므로 스택오버플로우 고려 x, 바로 로컬변수로 선언
	queue<Point>myqueue;
	visited[srcRow][srcCol] = true;
	myqueue.push({srcRow,srcCol,0}); // 현재 위치에서 현재 위치까지 이동하기 위한 거리 0
	while(!myqueue.empty()){
		Point curr = myqueue.front();
		myqueue.pop();
		if(curr.row == dstRow && curr.col == dstCol){
			return curr.dist;
		} // 현재위치 == 도착점, 이동거리 반환 
		for(int i=0;i<4;i++)
		{
			int nr = curr.row + d[i][0], nc = curr.col + d[i][1]; //상하좌우 이동 
			if(nr<0 || nr>n-1 || nc<0 || nr>n-1) continue; // 현 위치가 n*n 범위를 벗어났는지 check
			if(visited[nr][nc]) continue; // 방문 여부 check 
			if(Board[nr][nc] == 1) continue; //벽이 있는지 check
			visited[nr][nc] = true;
			myqueue.push({nr,nc,curr.dist+1}); // 거리 한칸 더해준다. 
		}
	} 
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++){
			cin>>Board[i][j];
		}
	}
	int srcRow,srcCol, dstRow, dstCol; //시작점 도착점의 위치
	cin>>srcRow>>srcCol>>dstRow>>dstCol;
	cout<<bfs(srcRow,srcCol,dstRow,dstCol);
	
}

 다음과 같이 너비 우선 탐색을 활용하여 최단거리를 구할 수 있게 된다. dfs랑 코드상 차이는 없지만, 스택(LIFO(Last In First Out)) 대신 큐(FIFO(First In First Out))를 사용한다는 차이와 현재 위치와 거리를 지속적으로 기록해둔다는 차이가 있다. 

<참고자료 사이트>

https://www.youtube.com/watch?v=RxT7F6YA3TI&list=PL6YHvWRMtz7DS3hVaqMazHujPcKVfblQa&index=6