BFS

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

큐를 이용하여 BFS를 푸는 법

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복

이때 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다.

정석적 bfs 틀

bfs는 코딩테스트에 자주 출제되는 중요한 알고리즘이기 때문에 해당 틀을 달달 외우다시피 하는 것을 추천한다.

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

int board[502][502]; //그림
int isVisit[502][502]; //방문여부 저장

//아래 오른쪽 위 왼쪽
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 maxScale=0; //그림의 최대크기 
    int paintings=0; //그림 갯수
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            //0이거나 방문한 경우
            if(board[i][j]==0 || isVisit[i][j]) continue;
            
            paintings++;
            
            queue<pair<int, int>> Q;
            //1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
            isVisit[i][j]=1;
            Q.push({i,j});
            
            int scale =0; 
            while(!Q.empty()){
                scale++;
                // 큐에 들어있는 원소를 하나 뺄 때 마다 넓이를 1 증가시킴
                pair<int, int> current = Q.front(); 
                Q.pop();
                
                
                //2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
                for(int dir =0; dir<4; dir++){
                    //nx: 다음 x, ny: 다음 y
                    int nx = current.X + dx[dir];
                    int ny = current.Y + dy[dir];
                    
                    //범위 밖으로 벗어나지 않게 if문 걸어주기
                    if(nx <0 ||nx>=n || ny<0|| ny>=m) continue;
                    //방문했거나 색칠된 칸이 아닌경우
                    if(isVisit[nx][ny] || board[nx][ny]!=1)continue;
                    
                    isVisit[nx][ny] = 1; //다음칸 방문 명시
                    Q.push({nx, ny}); //큐에 push
                }
            }
            
            //(i,j)를 시작점으로 하는 bfs 종료
            maxScale = max(maxScale, scale);
        }
    }
    
    cout << paintings << '\n'<<maxScale;
    
    
}

bfs 응용

bfs 응용 1 - 다차원 배열의 거리측정

2178 미로탐색

미로탐색 바로가기

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

7576 토마토