(본 글 참조 : https://www.youtube.com/watch?v=ftOmGdm95XI&t=1s )

BFS(Breadth First Search)

[ Blood Fill과 BFS/DFS ]

• 블러드 필(Blood Fill)
  : 다차원 배열에서 연결된 영역을 찾는 유형

• BFS(넓이우선) / DFS(깊이우선)
  : 이러한 블러드 필을 해결하는 알고리즘

---

[ 설명 ]

• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
• 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘들 중 하나
• 시작 정점으로부터 가까운 정점을 먼저 방문 / 멀리 떨어져 있는 정점을 나중에 방문
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색
• 두 노드의 최단 경로 OR 임의의 경로를 찾을때 주로 사용
• 큐(Queue) 자료구조를 사용한다 - 선입선출(FIFO)

---

[ 원리 ]

---

[ 기본 Code ]

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
#define X first
#define Y second
int board[502][502];
bool vis[502][502];
int n = 7, m = 10;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    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];
            // nx와 ny에 대한 범위 검사를 먼저 해야 한다.
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            // 범위 검사 후에 반드시 vis와 board검사가 와야 한다.
            if(vis[nx][ny] || board[nx][ny] != 1) continue;
            vis[nx][ny] = 1;
            Q.push({nx,ny});
        }
    }
}

• utility 헤더에 pair을 이용해서 복수의 인자를 queue에 삽입
  * dx[4] 와 dy[4]는 해당 정점의 상/하/좌/우에 접근하기 위한 배열
• x가 행을 / y가 열을 의미

---

[ 자주 하는 실수 ]

1) 시작점에 방문했지만 표시를 남기지 않는 실수
2) 큐에 넣을 때 방문했다는 표시를 하지 않고 빼낼 때 방문했다는 표시를 할 때
     --> 같은 칸이 여러번 큐에 들어가는 경우가 생김
3) 이웃한 원소가 범위를 벗어났는지 체크하지 않는 실수

DFS(Depth First Search)

[ 설명 ]

• 깊이를 우선적으로 탐색
• DFS는 Stack 자료구조를 사용
• 기본 틀은 BFS와 같고 사용하는 자료구조만 바뀜
• DFS는 막힐 때 까지 탐색하기 때문에 재귀로 구현 가능!
• BFS와 달리 거리측정을 할 수 없다
  (일정하게 퍼지지 않기 때문)