[algorithm] 너비 우선 탐색(BFS)

들어가며

오늘은 알고리즘에 조금이라도 관심이 있고 코딩테스트를 준비하는 사람이라면

누구나 알만한 주제인 BFS에 대해 알아볼 것이다

BFS는 코딩테스트 단골 유형으로 출제되고 응용 문제도 많아서

BFS 코드의 기본 틀은 어느정도 암기를 해야 문제푸는데에 수월할 것이다

 

BFS란

BFS는 Breadth First Search의 약자로 너비 우선 탐색이라는 의미를 가진다

주어진 속성을 만족하는 노드를 찾기 위해 트리를 탐색하는 알고리즘이다.

출처 : 위키백과

 

너비 우선 탐색이라는게 무슨말인지 의문을 가질 수 있다

트리 구조에서 가로 방향을 너비라고하고 세로 방향을 깊이라고 한다

너비 우선 탐색은 같은 깊이의 가로 방향의 노드들을 전부 다 탐색하고

그 다음 깊이로 내려가 또 같은 깊이의 노드들을 탐색하는 방식이다

 

위의 사진을 예시로 들면

1 ->  2,3,4 -> 5,6,7,8 -> 9,10,11,12 순으로 탐색을 진행한다

 

여기까지가 이론이였고 이제 이를 코드로 표현할 수 있어야 한다

코드로 구현하기 위해서는 2차원 배열을 사용할 것이고 큐(queue)를 활용해야 한다

 

흐름은 아래와 같다

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

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

3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고,

    처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다

4. 큐가 빌 때까지 2번을 진행한다

 

즉 2차원 배열이므로 상하좌우로 인접한 칸들이 같은 깊이에 있다고 생각하면 된다

시작점으로부터 같은 거리에 있는 것들은 같은 깊이(레벨)에 있는 것이다

 

위의 흐름을 코드로 표현하면 아래와 같고

이 코드 흐름은 정석적인 구현이고 암기해주는게 정신건강에 좋을 것 같다

#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();
    for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
      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[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
      Q.push({nx,ny});
    }
  }
}

 

우선 while문을 보면 pair 를 사용한 것을 볼 수 있다

pair는 utility 헤더에 있고 두 자료형을 묶어서 가지고 있는 개념이다

값은 first,second로 호출할 수 있다

#define X first/ Y second를 한 것은 pair를 조금 더 편하게 쓰기 위함이다

 

전역변수들을 먼저 살펴보면

board는 말 그대로 판을 의미한다 board 원소 값이 1이면 접근가능, 0이면 접근 불가능이라고 가정한다

그다음 vis는 방문 여부를 나타내는 배열이다 방문했으면 값을 1로 바꿔 방문 표시를 남겨주는 것이다

n,m은 각각 행과 열의 길이를 의미하고 dx,dy는 상하좌우로 이동하기 위한 방향 벡터이다

 

이제 main()함수 안을 보면

시작 지점을 0,0으로 지정하고 vis[0][0]=1; 을 하여 방문 표시를 남기고 큐에 삽입한다

그 후 큐가 빌때까지 큐의 front를 꺼내어 cur에 저장하고 

cur로부터 상하좌우를 탐색하면서 범위 안에 들어오면서 이전에 방문한 칸이 아니고 접근 가능하면(board 원소값이 1)

방문 표시를 남기고 큐에 삽입한다

 

while문 안에 if문이 2개가 있는데 2개의 순서가 바뀌게 된다면

vis[-1][0]처럼 참조하면 안되는 엉뚱한 값을 참조하게 될 수 있어 런타임에러가 발생한다

그래서 범위를 꼭 우선적으로 확인해주는 것이 중요하다

 

마치며

오늘은 매우 중요한 주제인 BFS에 대해 공부했는데 개념만 들었을 때 도무지 무슨 말인지 감이 안잡혔는데

흐름을 코드로 구현해보고 여러 예시들을 보니 어느정도 이해가 되었다

코드로 구현하는 것도 처음엔 꽤 오래걸려서 계속 BFS 흐름을 떠올리면서

이렇게도 써보고 저렇게도 써보니 뭐가 문제인지 알게되고 머리 속에서 흐름이 잡히는 느낌이였다

응용을 한다면 한없이 어려워질 수 있는 개념이라서 관련 문제들을 많이 풀어보면서 

BFS 기본 틀을 최대한 암기하고 손에 익히는 것이 중요하다고 생각했다