[바킹독의 실전 알고리즘] 0x09강 - BFS

1. 알고리즘 설명

 

BFS(Breadth First Search. 너비 우선 탐색)

그래프에서 모든 노드를 방문하기 위한 알고리즘. 그래프는 정점과 간선으로 이뤄져있음. 

하지만 우린 여기서 다차원 배열로 BFS를 이해하고 활용할 예정!

 

2. 예시

 

초기 세팅에서 BFS는 좌표를 담을 큐가 필요함. BFS 알고리즘이 시작되면 우선 (0,0)을 방문했다는 표시를 남기고 해당 칸을 큐에 넣음. 

 

BFS 과정

 

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

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

3) 해당 칸을 이전에 방문했을 시 아무 것도 하지 않고, 처음으로 방문했을 시 방문했다는 표시를 남기고 해당 칸을 큐에 삽입

4) 큐가 빌 때까지 2번 반복

 

참고로 BFS의 시간복잡도를 생각해보면 방문 표시를 남기기 때문에 모든 칸(좌표)은 큐에 1번씩만 들어감. 그렇기 때문에 시간복잡도는 칸이 N개일 때 O(N)이 됨. 행이 X개이고 열이 Y개이면 시간복잡도는 O(XY).

 

BFS 과정을 그림으로 확인을 해보고 싶다면 바킹독님 영상이나 블로그를 참조하기. (파란 칸이 방문해야될 곳이고 빨간 칸이 방문하지 않는 곳이다!)

 

BFS 구현

 

BFS의 경우 구현 방식이 고정이 되어있기 때문에 거의 외우다시피 알고 있어도 좋음. 특히, 삼성 A형을 치기 위해서는 BFS를 숙달해야 한다고 함.

 

pair

 

본격적으로 BFS 코드를 보기 전, pair에 대해서 알아봐야 함.

 

pair란 utility 헤더 안에 있는 클래스로, 이를 이용하면 두 자료형을 묶어서 가지고 다닐 수 있음. algorithm이나 vector 헤더 파일에도 포함이 되어 있다고 함. 

#include <iostream>
#include <utility>

int main(void){
  pair<int,int> t1 = make_pair(10, 13); //int 타입 데이터 2개를 관리하는 pair 클래스 객체 t1 생성. 
  pair<int,int> t2 = {4, 6}; // C++11
  cout << t2.first << ' ' << t2.second << '\n'; // 4 6 
  if(t2 < t1) cout << "t2 < t1"; // t2 < t1
}

📌 Pair 관련 참고 자료

https://cplusplus.com/reference/utility/pair/pair/

https://ya-ya.tistory.com/91

 

아래는 큐로 구현한 BFS 코드임!

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

#define X first
#define Y second // pair에서 first, second를 편하게 쓰기 위해서 사용

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} }; // 1이 파란 칸, 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;
  vis[0][0] = 1; // (0, 0)을 방문했다고 명시
  Q.push({0,0}); // 큐에 시작점인 (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++){ // 상하좌우 칸을 살펴볼 것이다. 중요한 부분!! x가 행, y는 열
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) 
      	continue; // 범위 밖일 경우 넘어감
      if(vis[nx][ny] || board[nx][ny] != 1) 
      	continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우. 두 줄 위의 코드와 바꿔 쓰면 vis[-1][0] 같은 게 참조되어 런타임 에러 발생 가능
      vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
      Q.push({nx,ny});
    }
  }
}

 

BFS 코드를 짤 때 실수할 수 있는 부분

 

1) 시작점에 방문했다는 표시를 남기지 않음

2) 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남김

같은 칸이 큐에 여러 번 들어가게 되므로 시간 초과나 메모리 초과가 발생할 수 있음.

3) 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘 못함. 

앞 코드에서 nx, ny가 배열 바깥으로 벗어났는지에 대한 루틴을 빼먹었거나, 아니면 이상하게 구현을 한 상황을 의미함.