바킹독 0x09 BFS란?

 

알고리즘의 고비 라고 하는 BFS......

나는 매 하나하나 모든 게 다 고비였는데...

너무 큰 산이였는데..

이 산은 너무 커서 앞도 안 보인다....

과연 내가 이 산을 넘을 수 있을까..?

---

일단 시작하기 전에 BFS에 대해 살짝 정리해 보자.

 

BFS   Breadth Frist Search

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

 

너비를 우선으로 방문한다라..

 

생각을 해보면..

 

 

 

자 열심히 피피티에 그렸습니다.

0.0일 때

앞에 숫자는 행이고, 뒷 숫자는 열입니다.

 

우리는 이 넓은 땅에서 파란 칸을 확인하는 코드를 쓴다고 합시다.

 

우리는 그 확인을 위해 큐를 쓰지요

그래서 먼저 0.0을 방문하고 방문했다는 의미에서 큐에 넣습니다.

 

 

방문을 했죠.

이다음에는 큐가 빌 때까지

큐의 front를 빼며, 해당 좌표의 상하좌우를 확인하게 됩니다.

그와 동시에 살펴보면서 큐에 다시 넣어주는 작업을 하고요.

 

말로 이렇게 하면 어려우니 다시 그림으로 가봅시다.

 

먼저 큐의 front는 0.0이니 빼봅시다.

그리고 0.0의 상하좌우를 봅시다.

 

0.0에서 상하좌우는 0.1과 1.0 이렇게 두 곳 있죠!

둘 다 파란 칸이긴 하네요!
일단 두 곳을 큐에 넣습니다.

 

 

 

오케이 넣었습니다.

다음 front를 뺍니다. 0.1이죠

빼면서 이동해 봅시다.

 

자. 0.1에 왔습니다

갈 수 있는 상하좌우는 이렇게 삼각형으로 표시했어요.

근데 0.0은 이미 왔던 길이 긴 합니다. 그래서 pass

그리고 1.1을 보니 빨간 칸입니다. 그래서  pass

그러면 0.2만 남네요.

그러면 0.2를 표시해 주고 큐에 넣습니다.

 

 

이렇게요

 

자 그럼 이제 패턴이 대충 구상이 가나요?!

1. 파란색이면서 인접하지 않은 곳을 큐에 넣는다.

2. 큐의 맨 앞에 것을 빼면서 그곳의 상하좌우를 확인한다.

3. 다시 1로 돌아간다.

 

헷갈리면 한번 더해봅시다.

 

이제 어디로 가야 할까요. 1.0으로 가야겠죠!

 

 

자 인접한 친구들을 봅시다.

일단 0.0은 지나왔으니 할 필요가 없고. 1.1은 빨강이라 필요 없고

남는 곳은 2.0 하나네요.

 

 

자

다음 0.2를 뺄 차례네요!

 

 

오.. 갈 곳이 없네요!

0.1은 이미 갔고 나머지는 빨간색이니까요! 그럼 이렇게 끝!

 

다음 2.0으로 갑니다.

 

 

 

이번엔 갈 곳이 두 곳이나 있네요!

3.0과 2.1 두 곳을 둘 다 넣어줘요.

 

 

뒤에는 계속 같은 패턴이니까 대충 알겠죠?!

이렇게 해주면 됩니다!!

 

요호!

이미 갔던 칸은 다시 가지 않기 때문에

좌표는 큐에 딱 한 번만 들어갔다가 나가게 된다.

그래서 시간복잡도는 O(n)이다.

즉 열이 R이고 행이 C면 O(RC)이다.

 

자 그러면 이렇게 하나씩 채워가는데

음? 여기 0.4는 어떻게 가지?!

싶을 것이다.

 

그다음에 돌다 보면 파란색인 칸을 발견할 것이고

다시 큐에 넣고 하면 될 것!

 

---

 

이제 이걸 코드로 하려면

일단 꼭 알아야 하는 부분이 있다.

 

1. 행과 열 즉 두 개의 숫자가 필요하기 때문에

pair이라는 STL을 써야 한다.

두 자료형을 묶을 때 사용한다.

pair <int, int> 라고 쓴다.

pair<int,int> t2 = {4,6}

이렇게 추가가 가능하다.

앞에 친구를 first, 뒤에 친구를 second라고 부른다.

 

사실 스택에서도 썼었지만..ㅎㅅㅎ

BFS에서는 필수니까 한번 더!

 

2. 상하좌우를 움직이는 코드가 필요하다.

 

이건 외워야 한다.

외워 야한 거 같다.

외울 것이다.

주문 외운다.

 

일단 상하좌우를 표시하기 위해

dx, dy를 만든다

int dx [4] = { 1, 0, -1, 0 };

int dy [4] = { 0, 1, 0, -1 };

이것을 미리 선언해 준다.

 

그다음에 for문으로 지금 현 위치에다가 이 dx, dy를 더해줘야 한다.

 

for( int dir = 0; dir < 4; dir++)

int nx = cur.first + dx [dir]

int ny = cur.secont + dy [dir]

if( nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;

if( vis [nx][ny] || board[nx][ny] != 1) continue;

vis[nx][ny] = 1;

Q.push({nx, ny});

 

자, 한 줄씩

for( int dir = 0; dir < 4; dir++)

상하좌우기 때문에 4개!

 

int nx = cur.first + dx [dir]

현 위치 cur ( Q.front ) 값에 dx값 더해주기 ( 상 하 )

 

int ny = cur.secont + dy [dir]

현 위치 cur ( Q.front ) 값에 dx값 더해주기 ( 좌 우 )

 

if( nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;

범위입니다. 맨 끝이냐? 혹은 nx가 0보다 작을 순 없으니까.. y도 마찬가지고

이 범위를 먼저 해준다음에 vis와 board를 해줘야 한다!!!

 

if( vis [nx][ny] || board [nx][ny]!= 1) continue;

board는 그림판, vis는 갔냐 안 갔냐 bool값으로 표현하는 배열

즉,

board : 보드판이 파랑이냐? 빨강이냐?

와

vis :  여기 한번 온 적 있냐 없냐

 

vis [nx][ny] = 1;

이제 와봤으니 1로 바꿔주고

 

Q.push({nx, ny});

값을 push 해서 넣어준다. 이따 또 상하좌우 할 때 써야 하니까!

 

이렇게 된다.

 

그래서 전체적인 베이스 코드는

#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});
    }
  }
}

 

---

 

.....................

기본이라는데..

나는 아직 기본도 없다.

계속 이해해야 할 필요성이 있다.

그리고 BFS의 주문..

dx, dy

nx, ny

if문 조건들..

 

잘 외워보도록 하자! 

얍!!