BFS란?

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

BFS의 예시

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

• 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개 일때 O(N)

BFS에 쓰이는 STL

• utility 헤더에 있는 pair두 자료구조를 묶어서 값을 넣어줄 수 있음.

  대소 관계가 설정되어있어 알아서 앞의 값을 비교하고 그 다음 뒤의 값을 비교함.

  pair<int,int> t1 = make_pair(10,13); // 값 초기화
  pair<int,int> t2 = {4,6}; // C++ 11 이상
  cout << t2.first << ' ' << t2.second //값의 접근
  

BFS의 정석적인 구현

• BFS는 정석적인 구현 형태가 있어서 숙달하고 있는 것이 중요하다.

  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};
  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; //이미 방문했거나 1이 아닌 경우에도 Q에 푸쉬 하지 않는다.
          vis[nx][ny] = 1; //board[nx][ny] 값이 1인 경우 방문했다는 표시 후에
          Q.push({nx,ny}); //큐에 값을 추가한다 (다음 순회를 위한)
      }
  }
  

BFS를 구현할 때 실수하는 점 몇가지

1. 시작점을 Queue에 넣지만 방문했다는 표시를 남기지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다. 이렇게 되면 같은 칸이 큐에 여러번 들어가게 되어서 시간초과나 메모리 초과 발생가능성 있음.
3. nx, ny가 배열을 벗어났을 때에 대한 확인을 잘못했다.