BFS(Breadth First Search)

: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

BFS

#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[502][502] = {};
bool vis[502][502]; // visit
int n = 7, m = 10;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 }; //주위 상하좌우에 요소들에 접근하기 위한 배열
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue<pair<int, int>> q;
	vis[0][0] = 1;
	q.push({ 0, 0 });
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		cout << '(' << cur.X << ", " << cur.Y << ") -> ";
		for (int dir = 0; dir < 4; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; //범위를 꼭 먼저 확인
			if (vis[nx][ny] || board[nx][ny] != 1) continue;
			vis[nx][ny] = 1; 
			q.push({ nx,ny });
		}

	}
	
}

🍀 board에는 1이면 탐색 가능한 칸, 0이면 탐색 불가능한 칸인데 코드에선 입력코드는 생략함.

dx[] , dy[] 배열은 상하좌우 칸을 확인하기 위한 배열이다.
📌 if조건문의 순서가 바뀌면 안된다. 꼭 먼저 범위 내에 들어오는지 확인한 후에 vis, board 배열값을 봐야한다. vis[-1][0]같은 경우 런타임 에러가 발생하기 때문이다.

👨🏻‍🏫 오류가 발생하는 포인트
1. 시작점에 방문했다는 표시를 남기지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다. -> 이렇게 되면 같은 칸이 큐에 여러 번 들어가게 되어서 시간 메모리 초과가 발생 할 수 있다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.

⭐ BFS 성질 : BFS를 돌때 큐에 쌓이는 순서는 반드시 거리 순이게 된다. 거리순으로 방문한다.
👉🏻 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다."

DFS (Depth First Search)

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘.

📌 BFS는 큐를 사용하고 DFS는 스택을 사용한다.
원소 하나를 빼내고 주변을 살펴본다는 알고리즘의 흐름은 똑같다.
bfs dfs 모두 비록 최종적인 방문 결과는 똑같더라도 방문 순서에서 아주 큰 차이가 있다.

👉🏻 DFS에서는 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다."라는 성질이 성립하지 않는다. 그래서 거리를 계산할 때는 DFS를 사용할 수 없다.

👨🏻‍🏫 그러면 결국 우리는 다차원 배열에서 굳이 BFS 대신 DFS를 써야하는 일이 없다. Flood Fill은 BFS, DFS중에 어느 것을 써도 상관 없는데 거리측정은 BFS만 할 수 있으니 DFS를 쓸 일이 없다.
그래서 다차원배열에서 순회하는 문제를 풀때 BFS만 쓰면 된다.
DFS는 나중에 그래프와 트리구조를 배울 때 필요하다.

---

source : 바킹독의 실전 알고리즘 0x09강