[알고리즘] BFS(너비 우선탐색)

jaehyeonLee·2024년 11월 19일

그래프

목록 보기

3/5

BFS(너비우선탐색)

BFS란 루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다
이전에 DFS는 루트노드에서 깊게 들어가며 모든 정점을 순회하는 방법이라고 생각을하면 BFS는 루트노드에서 넓게 들어가며 모든 정점을 순회하는 방법이라고 생각을하면된다

BFS 특징

이전에 DFS같은경우는 재귀를 활용하였으나 BFS같은경우는 Queue가 주로 사용이된다
DFS에서 처럼 모든 정점을 방문을 해야하다보니 무한루프의 가능성이 있어 방문한 정점인지 아닌지를 체크해줄 필요가 있다

BFS 과정

현재 이렇게 그래프가 구성되어 있다고 가정을 하겠다

루트인 A를 먼저 방문을 한다 VISITED[A]는 true 가 된다 이후 인접한 노드인 B와 C를 방문 하여 B와 C를 Queue 에 넣어준다
다음 정점을 찾기 위해 queue를 dequeue 하여 B를 받는다

정점 B에서 방문하지 않는 모든 인접 정점 D,E를 방문하고 큐에 넣어준다

정점 C에는 방문하지않은 인접정점이 없으므로 너비 우선탐색을 계속 할 다음정점을 찾기위해 큐를 dequeue 하여 D를 받는다

정점 D에 인접정점들을 처리했으므로 너비 우선 탐색을 계속 할 다음정점을 찾기 위해 큐를 deQueue 하여 E를 받겠지만
정점 E에는 방문하지 않은 인접 정점이 없으므로 , 너비 우선탐색을 계속 할 다음 정점을 찾기 위해 큐를 deQueue 하여 G를 받는다

정점 G에 대한 인접 정점들을 처리했으므로 너비 우선 탐색을 계속 할 다음 정점을 찾기 위해 큐를 deQueue 하여 F를 받는다

정점 F는 모든 인접 정점을 방문했으므로 너비 우선 탐색을 계속할 다음 정점을 찾기 위하지만 queue는 공백이므로 너비 우선탐색이 종료가 된다

문제 풀이(그림)

이번에도 DFS 와 같이 백준 에서 문제를 가져와 문제풀이를 하면서 BFS를 구현해보도록 하겠다 (백준 1926 : 그림)

1 : 색칠된 부분 , 문제에서 찾아야하는 부분
0 : 색칠이 안된부분 , 문제에서는 찾을 필요가 없는 부분
이번에는 이차원 배열을 이용한 인접행렬로 문제가 진행되는것으로 보이고 queue 에는 x좌표와 y좌표를 함께 넣어줄수 있도록 해야한다

#include "bits/stdc++.h"
using namespace std;
#define SIZE 501
struct Node
{
	int first;
	int second;
};
int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,1,-1 }; //좌우 탐색
int buffer[SIZE][SIZE]; bool visited[SIZE][SIZE] = { false, };
int n, m, result,cnt=0;
bool Check(int x, int y) //배열 BOUND 벗어나는지 확인 
{
	if (x < 0 || x >= m || y < 0 || y >= n)return false; 
		
	return true;
}
void BFS()
{
	queue<Node>que;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//1인지 확인&&방문한 곳인지 확인
			if (buffer[i][j] == 1 && !visited[i][j])
			{
				cnt++; //카운트 증가= 구역 하나 추가 
				visited[i][j] = true; //방문 확인
				int area = 1; 
				que.push({ i,j });

				while (!que.empty())
				{
					int y = que.front().first; 
					int  x= que.front().second;
					que.pop();
					for (int k = 0; k < 4; k++) //인접 정점 확인 
					{
						int next_x = x + dx[k];
						int next_y = y + dy[k];
                        //배열의 범위에서 벗어나는지 , 방문 했는지 , 1이 있는 지 확인 
						if (Check(next_x, next_y) && !visited[next_y][next_x]&& buffer[next_y][next_x]==1)
						{
							visited[next_y][next_x] = true;
							que.push({next_y,next_x});
							area++;
						}
					}
				}
				result = max(area, result); //가장 큰 넓이 구하기 위함 
			}
		}
	}

}
void Insert()  //입력함수 
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> buffer[i][j];
		}
	}
	BFS();
	cout << cnt << '\n' << result << '\n';
}
int main()
{
	Insert();
	return 0;
}

변수
cnt 는 1의 그룹의 개수를 카운트 해줄 변수이다
result 는 1의 그룹의 넓이중 가장 큰 넓이가 들어갈 변수이다
dx 와 dy 배열은 상하좌우를 탐색하기 위함인데 이는 그래프로 생각을하면 인접한 정점들을 탐색해주기 위함이다

함수
Insert는 입력값을 받기 위한 함수이다
Check함수는 배열의 인덱스에서 벗어남을 방지하기 위함 함수이다
BFS 함수는 이문제에서 핵심인 함수이다

이렇게 3x3 배열이 있다고 가정하겠다
배열의 인덱스(0,0)에는 1이 들어가있기에 queue 에 들어간다
y=0,x=0 으로 deque를 해주고
dx dy를 통해 인접한 인덱스들을 탐색한다
(0,1)에 1이 있는것을 확인하였으니 queue 에 들어가고 이와 같은 방식으로 (1,1) -> (2,1) -> (2,2) 인덱스들을 전부 탐색할수있게 된다

위 문제에서 0은 굳이 visited를 해주지 않아도 탐색이 가능하다