바킹독의 실전 알고리즘 : BFS

바킹독의 실전 알고리즘 : BFS

알고리즘 설명

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

본디 BFS는 그래프라는 자료구조에 모든 노드를 방문하기 위해 제안된 알고리즘이다.

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

int main(void){
    pair<int,int> t1=make_pair(10,13);
    pair<int,int> t2={4,6};
    cout<<t2.first<<' '<<t2.second<<'\n';
    if(t2<t1) cout<<"t2<t1";
}

utility 헤더에 있는 pair는 두 자료형을 묶어서 다닐 수 있다. BFS는 정말 숙달되도록 잘 알아야 한다. 그 냥 외 우 는 걸 추 천 했 으 니
외우자..

{% raw %}

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

#define X first
#define Y second //X,Y를 상수로

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;

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; //int 두 개를 페어로 넣을 수 있는 큐 선언
    vis[0][0]=1; //이게 시작점 표시인듯
    Q.push({0,0}); //그리고 큐에 시작점 값을 넣기

    while(!Q.empty()){
        pair<int,int> cur=Q.front(); Q.pop; //현재 위치는 cur, 그리고 큐에서 값 빼기
        cout<<'('<<cur.X<<", "<<cur.Y<<") -> ";
        for(int dir=0;dir<4;dir++){ //디렉팅
            int nx=cur.X+dx[dir]; //아 3방향으로 다 돌아보는군
            int ny=cur.Y+dy[dir];
            if(nx<0||nx>=n||ny<0||ny>=m) continue; // 없는 위치이면 넘기고
            if(vis[nx][ny]||board[nx][ny]!=1) continue; // vis에 이미 방문한 표시가 있으면 넘기고
            //근데 윗줄에서 board 배열의 역할은 뭐지? -> 아 예시 그림에서 주어진 파란 칸인지 범위 확인
            vis[nx][ny]=1; // 위 조건에 부합하지 않으면 얘도 vis 넣고
            Q.push({nx,ny}); //큐에 넣고
        }
    }
}

{% endraw %}

음 어렵군. 일단 본문 글 보기 전에 내가 코드 리뷰로 주석 달아보자.

1. 내가 주석 달아보고
2. 본문 읽으면서 보충하기

BFS를 구현할 때 짚어야 할 부분

1. 시작점에 방문했다는 표시를 남기지 않는다. -> 시작점 두 번 방문할 수도 있음
2. 큐에 넣을 때 방문했다는 표시 대신 빼낼 때 방문했다는 표시를 남겼다. -> 같은 칸이 큐에 여러 번 들어갈 수 있음
3. 이웃한 원소가 범위 외인지 체크를 잘못했다. -> 이건 뭐..

1926 : 그림

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

#define X first
#define Y second

int board[501][501];
bool vis[501][501];

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

    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cin>>board[i][j];
    }

    int max_paint=0;
    queue<int> paint;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(board[i][j]==0 || vis[i][j]==1) continue;
            vis[i][j]=1;
            queue<pair<int,int>> Q;
            Q.push({i,j});
            int vis_sum=1;

            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];

                    if(nx<0 || nx >(n-1) || ny<0 || ny > m-1) continue;
                    if(board[nx][ny]==0) continue;
                    if(vis[nx][ny]==1) continue;

                    vis[nx][ny]=1;
                    Q.push({nx,ny});
                    vis_sum++;
                }
            }
            paint.push(vis_sum);
            if(max_paint<vis_sum) max_paint=vis_sum;
        }
    }
    cout<<paint.size()<<'\n'<<max_paint;

}

나 혼자서 풀지는 못하고 BFS 예제 보면서 응용해 풀었다.. 코드 작성에 익숙해져야 할듯.. 이따가 집 가서 기본 코드 한 번 더 복습하기.

응용1 - 거리 측정

2178번

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

string tmp[101];
int board[101][101];

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

    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>tmp[i]; //string형 tmp에 다 받기 
    for(int i=0;i<n;i++) fill(board[i],board[i]+m,-1); //board에 다 -1로 채우기 
    queue<pair<int,int>> Q;
    Q.push({0,0}); // 0,0부터 시작 (1,1)에서 출발하는 문제이니까 
    board[0][0]=1; //방문 시작 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-1||ny<0||ny>m-1) continue;
            if(board[nx][ny]>0 || tmp[cur.X][cur.Y]!='1') continue; // tmp에서 1이 아니거나 board가 양수칸이거나 

            board[nx][ny]=board[cur.X][cur.Y]+1; //이전 칸의 누적칸 + 1칸 
            Q.push({nx,ny});
        }
    }
    cout<<board[n-1][m-1];
}

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

7576번

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[1001][1001];
int vis[1001][1001];

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

    int n,m;
    queue<pair<int,int>> Q;
    cin >> m >> n;
    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) vis[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-1||ny<0||ny>m-1) continue;
            if(vis[nx][ny]>=0) continue;

            vis[nx][ny]=vis[cur.X][cur.Y]+1;
            Q.push({nx,ny});
        }
    }

    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]==-1){
                cout<<-1;
                return 0;
            }
            ans=max(ans,vis[i][j]);
        }
    }
    cout<<ans;
}

시작점이 여러개일 때는 그냥 while문 돌리기 전에 큐에 시작점들을 다 넣고 시작하면 된다!

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

4179번인데 한 번 고민을 해보래서 좀 그려지는 게 있나 확인해보자.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

string board[1002];
int dis1[1002][1002];
int dis2[1002][1002];

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);
    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++){
        fill(dis1[i],dis1[i]+m,-1);
        fill(dis2[i],dis2[i]+m,-1);
    }

    for(int i=0;i<n;i++) cin>>board[i];

    queue<pair<int,int>> Q; 
    queue<pair<int,int>> fire;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(board[i][j]=='F'){
                fire.push({i,j});
                dis1[i][j]=0;
            }
            if(board[i][j]=='J'){
                Q.push({i,j});
                dis2[i][j]=0;
            }
        }
    }

    while(!fire.empty()){
        auto cur=fire.front(); fire.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(dis1[nx][ny]>=0 || board[nx][ny]=='#') continue;

            dis1[nx][ny]=dis1[cur.X][cur.Y]+1;
            fire.push({nx,ny});
        }
    }

    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){
                cout<<dis2[cur.X][cur.Y]+1;
                return 0;
            }

            if(dis2[nx][ny]>=0 || board[nx][ny]=='#') continue;
            if(dis1[nx][ny]!=-1&&dis1[nx][ny]<=dis2[cur.X][cur.Y]+1) continue;
            dis2[nx][ny]=dis2[cur.X][cur.Y]+1;
            Q.push({nx,ny});
        }
    }
    cout<<"IMPOSSIBLE"<<'\n';
}

이건 혼자 삽질하다가 못풀어서 해설 봤다...

응용4 - 1차원에서의 BFS

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

int vis[100001];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N,K;
    cin>>N>>K;

    fill(vis,vis+100001,-1);
    int d[4]={-1,1,2};
    queue<int> Q;
    Q.push(N);
    vis[N]=0;

    //아래 예외 케이스
    if(N==K){
        cout<<0;
        return 0;
    }

    while(!Q.empty()){
        auto cur=Q.front(); Q.pop();
        for(int dir=0;dir<3;dir++){
            int nx;
            if(d[dir]==2) nx=d[dir]*cur;
            else nx=cur+d[dir];

            if(nx<0 || nx>100000) continue;
            if(vis[nx]>=0) continue;

            if(nx==K){
                cout<<vis[cur]+1;
                return 0;
            }

            Q.push(nx);
            vis[nx]=vis[cur]+1;

        }

    }
}

이건 어쩌다보니 나 혼자 풀었는데 TC만 맞고 계속 틀렸대서 제미나이한테 물어봤다. 예외케이스를 하나 생각 안 해서 생긴 문제였다... TC를 잘 정의하는 것이 중요해보인다.