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

</aside>

• 좌표를 담을 큐 가 필요

  • queue 자료형 사용

• 예시)

  1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
  2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
  3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
  4. 큐가 빌 때까지 2번을 반복 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N).

  #include <bits/stdc++.h>
  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(void){
  	ios_base::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});
  		}
  	}
  }
  

흔히 하는 실수)

1. 시작점에 방문했다는 표시를 남기지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남긴다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.