BFS

BFS란 무엇인가?

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

- 그래프라는 자료구조에서 모든 노드를 방문하기 위한 자료구조

 

문제풀이에서 BFS의 활용방식은?

-인접한 칸에 대해서 색칠하는 Flood-Fill, 최단거리 문제 혹은 움직임이 정해져 있는 경우

 

Code

#define X fisrt
#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(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();
        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});
            }
        }
}