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

0x00 알고리즘 설명

 

정점과 간선으로 이루어진 자료구조인 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다.

 

 

 

0x01 예시

원리를 이해해보자

 

우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다.

 

 

첫 시작(큐의 front)을 기록해놨으면 pop을 하고 그 점으로부터의 상하좌우 칸을 보는데, 이 중에서 파란색 칸이면서 아직 방문하지 않은 칸을 찾을것이다.

 

 

 

위 상황을 보면 (0,0)과 상하좌우로 인접한 (0,1)과 (1,)은 모두 파란칸이면서 방문하지 않았다. 그래서 이 2개의 칸에 방문해서 기록을 해두고 큐에 넣게된다.

 

 

 

이제 (0,1) 기준으로 다음 방문할 칸을 선별한다. (0,1)이 기준이 되었으니 큐에서 (0,1)을 pop한다. 저 점을 기준으로 다음으로 방문할 칸은 (0,2)가 되겠다.

 

 

 

(0,2)에 방문한 기록을 해두고 큐에 넣게된다. 다음으로는 큐의 front인 (1,0)기준으로 방문할 칸을 선별하게 될것이고 (1,0)을 pop하게 될것이다.

 

계속 이런식으로 큐의 front를 pop하고 인접한 칸 중에서 방문하지 않은 파란색 칸에 표시를 남기고 큐에 넣어주면 될것이다.

 

 

 

이렇게 큐가 빈 순간 과정은 종료되고 (0,0)과 상하좌우로 이어진 모든 파란 칸을 방문할 수 있었다.

 

정리하자면 아래와 같다.

만약 행이 R개, 열이 C개이면 시간복잡도는 O(RC)가 될 것이다.

 

 

 

 

pair

 

BFS를 구현할 때 큐에 좌표를 넣어야 하는데, 이때 pair를 쓸 것이다.

 

값의 접근은 각각 first, second를 부름으로서 가능하고 또 pair에는 미리 대소 관계가 설정되어 있어서 편하다. 알아서 앞쪽의 값을 먼저 비교하고, 이후 뒤쪽의 값을 비교한다.

이 때 first와 second를 짧게 이용하기 위해 x와 y로 정의한다고 선언 후 이걸로 사용한다.

 

make_pair로 값을 넣거나, C++11 이상에서는 그냥 중괄호로 쉽게 만들 수 있다.

 

 

 

 

 

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++){ // 상하좌우 칸을 살펴볼 것이다.
      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});
    }
  }
}

 

 

 

오류가 나는 사례들

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

 

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

 

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

 

 

 

 

 

 

 

기본 문제

BOJ 1926번:그림

 

 

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502];
bool vis[502][502];
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
        }
    }
    int mx = 0;
    int num = 0;
    ///////////////////////// 입력받은 수로 도화지 완성
    for(int i =0; i < n; i++){
        for(int j=0; j<m; j++){
            if(board[i][j] == 0 || vis[i][j] == 1) continue;
            num++;
            queue<pair<int,int>> Q;
            vis[i][j] = 1;
            Q.push({i,j});
            int area =0;
            while(!Q.empty()){
                area++;
                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];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    Q.push({nx,ny});
                }
            }
            mx= max(mx, area);
        }
    }
    cout << num << '\n' << mx;
}

 

 

 

 

 

 

 

 

0x02 응용1 - 거리 측정

BOJ 2178번:미로 탐색

 

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102]; //입력받을때 한 줄씩 받냐, 보드 자체를 입력받냐에 따라 []개수가 달라지고 for문 개수도 달라짐
int dist[102][102];
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
       cin >> board[i];
    for(int i = 0; i < n; i++)
        fill(dist[i],dist[i]+m, -1);
    queue<pair<int,int>> Q;
    Q.push({0,0});
    dist[0][0] = 0;
    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        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(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue;
            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
            Q.push({nx,ny});
        }
    }
    cout << dist[n-1][m-1]+1; //반드시 길이 있다고 했기 때문에, 해당 목적지의 visited 배열의 값에 +1을 해준 것이 최종 거리.
}

 

 

 

 

 

 

0x03 응용2 - 시작점이 여러 개일 때

BOJ 7576번:토마토

 

 

 

#include <bits/stdc++.h>
using namespace std;
int board[1002][1002];
int dist[1002][1002];
#define X first
#define Y second
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    queue<pair<int,int>> Q;
    for(int i=0; i < n; i++){
        for(int j=0; j < m; j++){
            cin >> board[i][j];
            if(board[i][j] == 1)
                Q.push({i,j});
            if(board[i][j] == 0)
                dist[i][j] = -1;
        }
    }          //위 코드가 시작지점 여러개일 때 설정법이다
    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        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(dist[nx][ny] >= 0) continue;
            Q.push({nx,ny});
            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
        }
    }        //위 코드가 bfs 돌린것이다. 
    int cnt = 0;
    for(int i=0; i < n; i++){
        for(int j=0; j < m; j++){
            if(dist[i][j] == -1){
                cout << -1;
                return 0;
            }
            cnt = max(cnt, dist[i][j]);
        }
    }
    cout << cnt;
}

 

 

 

 

 

 

 

0x04 응용3 - 시작점이 두 종류일 때

BOJ 4179번:불!

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int R, C;
int dist1[1002][1002];
int dist2[1002][1002];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            dist1[i][j]=-1;
            dist2[i][j]=-1;
        }
    }
    for(int i =0; i < R; i++)
        cin >> board[i];
    queue<pair<int,int>> Q1;    //불
    queue<pair<int,int>> Q2;    //지훈이
    //불, 지훈이 시작점 큐넣기
    for(int i =0; i < R; i++){
        for(int j =0; j < C; j++){
            if(board[i][j] == 'F'){
                dist1[i][j] = 0;
                Q1.push({i,j});
            }
            if(board[i][j] == 'J'){
                dist2[i][j] = 0;
                Q2.push({i,j});
            }
        }
    }
    //불 BFS
    while(!Q1.empty()){
        auto cur = Q1.front(); Q1.pop();
        for(int dir=0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >=  R || ny < 0 || ny >= C) continue;
            if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
            Q1.push({nx,ny});
        }
    }
    //지훈이 BFS
    while(!Q2.empty()){
        auto cur = Q2.front(); Q2.pop();
        for(int dir=0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C){
                cout << dist2[cur.X][cur.Y] +1;
                return 0;
            }
            if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
            if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue;
            dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
            Q2.push({nx,ny});
        }
    }
    cout << "IMPOSSIBLE";
}

 

 

 

 

 

 

 

 

 

 

0x05 응용4 - 1차원에서의 BFS

BOJ 1697번:숨박꼭질

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int vis[100005];
int n, k;
queue<int> Q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    fill(vis,vis+100004,-1);        //fill(vis의0번째,vis의100004번째(문법상 마지막은 빼야된다),-1);
    vis[n] = 0;
    Q.push(n);
    while(vis[k]==-1){
        int cur = Q.front(); Q.pop();
        for(int box : {cur-1, cur+1, 2*cur}){
            if(box<0 || box > 100000) continue;
            if(vis[box] != -1) continue;
            Q.push(box);
            vis[box] = vis[cur]+1;
        }
    }
    cout << vis[k];
}