BFS

자료구조를 배우면서 당시에 정말 이해가 잘 안됐던 부분이 있었는데 그것이 바로 BFS였다. DFS는 쭉 탐색하는 느낌이 있었지만 BFS를 어디에 쓰지? 라는 생각이 많았는데 공부하면서 BFS는 경로나 범위를 탐색하는 것처럼 다양한 방면에서 쓰인다는 것을 알게 되었다.

1. BFS란?

BFS란 Breadth First Search의 약자로 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 쉽게 표현하면 인접한 노드를 먼저 탐색하는 알고리즘이다.

알고리즘

1. 시작 노드를 큐에 넣는다.
2. 큐에서 원소를 꺼내어 인접한 노드를 탐색하고 넣는다.
   • 1) 인접한 노드가 위치(범위)를 확인한다.
   • 2) 해당 위치의 방문 여부를 확인한다.
3. 큐가 빌 때까지 2번 과정을 반복
   

2. 특징

• 장점

  1) 답이 여러 개인 경로에도 최단 경로임을 보장한다.
  2) 특정 범위나 영역 탐색에서 효율적이다.

• 단점

  1) 메모리 사용량이 많다.
  2) 해답이 없는 경우에도 유한 그래프라면 모든 노드를 탐색한 후 종료한다.

3. 코드

#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; // n = 행의 수, m = 열의 수
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;
  Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
  vis[0][0] = 1; // (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; // 이미 방문한 칸이거나 탐색할 칸이 아닌 경우
      Q.push({nx,ny}); // 인접 노드 추가
      vis[nx][ny] = 1; // 방문 갱신
    }
  }
}

4. 마무리

지난번 큐가 bfs에 쓰일 수밖게 없던 이유를 알게 된 것
같다. bfs를 구현하기 위한 알고리즘과 어떤 상황에서 쓰이는지에 대한 간략한 구성을 알게 되었다.
대표적으로 bfs를 활용한 문제로는 거리 측정, 여러 시작점 탐지 등 다양한 문제로 활용될 테니 많이 공부해 보며 게임에도 적용을 해봐야겠다.

Reference
[실전 알고리즘] 0x09강 BFS - BaaaaaaaarkingDog