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});
}
}
}