BFS (다차원 배열)

BFS(Breadth First Search)

• 너비 우선 탐색
• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
  • 원래 BFS는 그래프에서 모든 정점을 방문하기 위한 알고리즘이다.

알고리즘 순서

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김

2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행

3. 해당 칸을 처음 방문한다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 / 이전에 방문했다면 아무것도 하지않음

4. 큐가 빌 때까지 2번을 반복

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

시간 복잡도

• 방문 표시를 남기므로 모든 칸은 큐에 1번씩만 들어간다.
  따라서 시간복잡도는 칸이 N개일 때 O(N)이 된다.

• 만약 행이 R개이고, 열이 C개이면 O(RC) 가 된다.

BFS 구현

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

// 판. 1이면 데이터 있는 칸, 0이면 데이터가 없는 칸
int board[502][502] = {
	{1,1,1,0,1,0,0,0,0,0},
	{1,0,0,0,1,0,0,0,0,0},
	{1,1,1,0,1,0,0,0,0,0},
	{1,1,0,0,1,0,0,0,0,0},
	{0,1,0,0,0,0,0,0,0,0},
	{0,0,0,0,0,0,0,0,0,0},
	{0,0,0,0,0,0,0,0,0,0}
}; 
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;
  
  // BFS 탐색을 시작하는 칸을 (0,0)으로 잡았다.
  vis[0][0] = 1;
  Q.push({0,0});
  
  while(!Q.empty())
  {
    // 큐에 저장된 칸(좌표)을 꺼내와서 cur에 저장
    pair<int,int> cur = Q.front();
    Q.pop();
    
    cout << '(' << cur.X << ", " << cur.Y << ") -> ";
    
    // 처리할 칸(cur)의 상하좌우 칸에 대해 처리 
    for(int i = 0; i < 4; i++){ 
      int nx = cur.X + dx[i]; // 상하좌우 칸에 대한 좌표 데이터 저장
      int ny = cur.Y + dy[i];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;
      if(vis[nx][ny] || board[nx][ny] != 1)
        continue;
      
      vis[nx][ny] = 1; // 방문 처리하고 상하좌우 칸을 큐에 push
      Q.push({nx,ny});
    }
  }
}

참고 ( => BFS 구현시 자주하는 실수 유형 )

1. 시작점에 방문했다는 표시를 남기지 않는 경우

   • 이렇게 되면 시작점을 2번 방문할 수가 있다.

2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남기는 경우

• 같은 칸이 큐에 여러번 들어가게 되어서 런타임 에러 발생
• 큐에 넣는 즉시 바로 방문 처리할것!

3. 상하좌우 좌표(nx, ny)가 정상적인 범위를 벗어났는지에 대한 체크를 잘못한 경우