Wizley

Wizley

I think I wanna become Android developer for now

bfs는 이런식으로 풀더라

게시일:

OverView

bfs는 그래프 문제를 풀 때 기초가 되는 알고리즘으로 대부분의 쉬운 문제들은 bfs만 사용해도 풀 수가 있다.

dfs가 깊이 우선 탐색이라면 bfs는 너비 우선 탐색을 위해 사용된다. 어떤 한 정점으로부터 인접해있는 모든 정점을 같은 스테이지에 탐색을 하는 방식을 사용하기 때문이다. dfs의 경우 A라는 정점에 B, C, D라는 정점이 간선으로 연결되어있을 경우 A -> B -> A -> C -> A -> D의 형식으로 재귀로 순회를 하였었는데 이렇게 순회할 경우 깊이가 너무 깊은 경우에 목적지에 도달하지 못하거나 스택이 터져버리는 문제가 발생할 수 있다.

동작 원리

bfs는 이런 문제를 해결하기 위해 queue를 사용한다. 정점이 A를 기준으로 간선을 순회하며 도달할 수 있는 방문하지 않은 정점인 B, C, D를 큐에 넣은 뒤, 다음 loop에서 pop을 통한 순회를 진행한다. 하나를 기준으로 탐색을 하는 것이 아닌 갈 수 있는 모든 정점을 동시에 탐색하는 방식이라고 할 수 있다. 이런 특성 덕에 최단 거리 와 너비 관련 문제 유형에 자주 사용된다. 시작 정점을 기준으로 도달 정점으로 갈 수 있는 모든 경우를 정점을 기준으로 큐에 넣어서 탐색을 진행하기 때문에 언제나 최단 거리가 가중치가 동일한 경우에 보장되기 때문이다. 그렇기에 dfs보다는 bfs는 선호하는 편이다.

bfs

위키피디아에서 그림을 가져와보앗는데 a를 기준으로 도달할 수 있는 정점인 b,c 를 큐에 넣으며 다음 루프에서는 b,c로부터 도달할 수 있는 정점은 d,c,f,g를 큐에 넣는다. 이런 특성 덕에 정점 b로 도달할 수 있는 최단 거리는 3인 것이 보장되게 된다.

구현

이번에도 쉬운 문제를 풀면서 구현을 해보도록 한다.

연구소

아주 기초적인 bfs는 아니지만 bfs의 특성을 이해하기에 아주 좋은 예제이다. 문제를 보면 인접행렬로 입력값이 주어지고 각각의 칸은 빈칸, 벽 그리고 바이러스로 이루어져 있다. 핵심을 보면 바이러스는 벽을 제외한 빈 공간으로 퍼지는데 벽을 3개 세움으로써 바이러스가 퍼지지 않을 수 있는 최대 공간을 찾아라는 것이다.

풀이 방법을 떠올려보면 다음과 같다.

  1. 임의의 벽 3개를 세운다.
  2. bfs를 돌려서 바이러스가 번진 결과를 만든다.
  3. 안전 영역의 크기를 계산한다.

이 3단계를 모든 경우의 수에 대해서 반복을 하면 될 것 같다.

1단계 임의의 벽 3개를 세우기 위해서는 빈 공간에 대한 정보를 따로 저장할 필요가 있다.

for(int x=0; x<X; x++){
    for(int y=0; y<Y; y++){
        cin >> MAP[x][y];
        if(MAP[x][y] == VIRUS){
            V_VIRUS.push_back(make_pair(x,y));
        }
        else if(MAP[x][y] == SPACE){
            V_SPACE.push_back(make_pair(x,y));
        }
    }
}

입력값을 MAP이라고 가정하면 VIRUS의 위치인 2가 들어오는 경우와 빈 공간의 위치인 0이 들어오는 경우를 나누어서 vector에 그 좌표를 저장해준다. 이러면 VIRUS에 대한 bfs를 돌리거나 공간에 대한 임의의 3가지 경우를 선택하는 경우에 MAP을 순회할 필요가 없다.

vector<int> v;

for(int i=0; i<V_SPACE.size(); i++){
    if(i<3){
        v.push_back(0);
    }
    else{
        v.push_back(1);
    }
}

그 후 v라는 백터를 생성하게 되는데 조합을 만드는 위치를 지정하기 위하여 사용된다.

예를 들어 SPACE가 8개가 존재한다고 생각해보자.

1 1 1 0 0 0 0 0

8자리 중에서 3자리를 선택하기 위해 위와 같은 vector 배열을 생성하게 되고 next_permutation이 이 순열을 돌려서 8자리로부터 3자리를 뽑아준다.

0 0 0 0 1 0 1 1

예를 들어 next_permutation이 여러번 수행되면서 위와 같이 1의 위치가 변형되었다면 8자리 중에 5번째, 7번째 그리고 8번째에 위치한 V_SPACE의 값이 벽을 세울 위치가 되는 것이다.

do {
    V_COMBINATION.clear();
    for(int i=0; i<v.size(); i++){
        if(v.at(i)==0){
            V_COMBINATION.push_back(V_SPACE[i]);
        }
    }

    for(int i=0; i<V_COMBINATION.size(); i++){
        MAP[V_COMBINATION[i].first][V_COMBINATION[i].second] = WALL;
    }

    bfs();

    for(int i=0; i<V_COMBINATION.size(); i++){
        MAP[V_COMBINATION[i].first][V_COMBINATION[i].second] = SPACE;
    }

} while(next_permutation(v.begin(), v.end()));

결국 순열 조합을 만들어서 해당 위치를 WALL로 변경하여 bfs를 돌리고 다시 SPACE로 변경하는 과정을 조합의 개수만큼을 반복하여 수행하는 것이다.

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

void bfs(){
    int MAP2[8][8] = {0,};

    for(int i=0; i<X; i++){
        for(int j=0; j<Y; j++){
            MAP2[i][j] = MAP[i][j];
        }
    }

    int VISITED[8][8] = {0,};
    queue<pair<int,int>> que;

    for(int i=0; i<V_VIRUS.size(); i++){
        VISITED[V_VIRUS[i].first][V_VIRUS[i].second] = true;
        que.push(V_VIRUS[i]);
    }

bfs는 위에서 설명했듯이 단계별로 가능한 모든 경우에 대해 탐색을 수행한다고 하였다. 이를 적용해보면 처음에 바이러스가 위치하는 공간들을 queue에 넣는 부분을 시작으로 탐색이 진행된다.

while(!que.empty()){
    int cur_x = que.front().first;
    int cur_y = que.front().second;
    que.pop();

    for(int i=0; i<4; i++){
        int nx = cur_x + dx[i];
        int ny = cur_y + dy[i];

        if(nx<0 || ny<0 || nx>=X || ny>=Y){
            continue;
        }

        if(!VISITED[nx][ny] && MAP2[nx][ny] == SPACE){
            VISITED[nx][ny] = true;
            MAP2[nx][ny] = VIRUS;
            que.push(make_pair(nx,ny));
        }
    }

}

처음에 바이러스가 위치한 영역들이 que에 들어가 있을 것이고 해당 영역들을 하나씩 pop하여 상하좌우로 탐색을 수행한다. 만약 상하좌우 중에 방문하지 않았으며 빈 공간(SPACE) 인 경우 que에 해당 부분을 추가하며 VIRUS로 최신화를 해준다.

처음에 push된 바이러스의 시작 위치에 대한 탐색이 완료되고 나면 그 위치로부터 도달한 que에 push된 빈공간들이 다시 순회가 되며 더 이상 탐색을 진행할 곳이 없어서 que가 빌 때까지 수행이 된다.

int count=0;
for(int i=0; i<X; i++){
    for(int j=0; j<Y; j++){
        if(MAP2[i][j] == SPACE){
            count++;
        }
    }
}

탐색이 완료되면 빈 공간으로 남아있는 위치를 카운트하여 최댓값을 유지해주기만 하면 된다.

과정을 그림으로 간소화해보면 다음과 같다

2 0 0 0 
0 0 1 0 
0 1 1 0 
0 1 0 2

위와 같은 상태가 있다고 해보자. 임의의 빈 공간 세 곳에 벽을 세운다.

2 0 W 0 
0 0 1 0 
W 1 1 0 
0 1 W 2

위의 그림의 W가 임의로 세운 벽이다. 이제 바이러스가 상하좌우로 퍼져나가는 것을 bfs로 시뮬레이션한다.

V 0 W 0 
0 0 1 0 
W 1 1 0 
0 1 W V

가장 먼저 que에 push가 되는 것은 바이러스의 처음 위치들이다. 맨 왼쪽 상단의 V와 하단의 V가 이에 해당 된다고 할 수 있다. 이로써 초기 상태인 큐에는 두 좌표가 들어있다.

V V W 0 
V 0 1 0 
W 1 1 V
0 1 W V

이제 que에서 요소들이 하나 씩 pop되면서 상하좌우로 탐색을 진행하게 되고 영향을 받게되는 공간들이 V상태로 변환되고 que에 push되게 된다. 초기에 큐에 존재하던 두 좌표가 pop되어 처리된 후의 상태는 위와 같고 새로 V상태가 된 좌표 3개가 que에 남아있게 된다.

V V W 0 
V V 1 V 
W 1 1 V
0 1 W V

다시 pop이 수행되고 나면 위와 같은 상태가 된다. 영향을 받게 되는 좌표는 2곳이므로 que에는 2곳이 남아있게 된다.

V V W V
V V 1 V 
W 1 1 V
0 1 W V

탐색을 다시 진행하면 맨 오른쪽 상단이 마지막으로 V로 변경되게 되고 더 이상 탐색할 곳이 없기 때문에 que가 비게 된다. 그리고 남아잇는 빈 공간은 한 개라는 사실을 알 수 있게 된다. bfs를 통해 바이러스가 퍼지는 것을 시뮬레이션 할 수 있을 뿐만 아니라 만약 바이러스가 옆 공간으로 퍼지는 경우에 걸리는 시간이 각각 1초라는 조건이 있으면 3초만에 바이러스가 퍼질 수 있는 모든 공간으로 퍼진다는 사실 또한 알아낼 수 있다. 이와 같이 bfs를 통해 탐색 뿐만 아니라 거리가 동일할 경우에 최단 거리를 구할 수도 있다.

장단점

장점은 역시나 최단 경로를 보장한다는 것이다. 모든 정점들간의 거리가 동일한 경우에는 결국 특정 정점까지 도달할 수 있는 최소 간선의 개수가 최단 거리이기 때문에 dfs로는 도달하면 중단되는 특성에 의해 보장되지 않던 최단거리가 bfs에서는 보장되기에 시뮬레이션을 할 때 활용도가 높다.

하지만 단점도 물론 존재하는데 큐와 같은 자료구조로 좌표에 대한 정보를 저장해야 되기 때문에 맵이 클 경우에 많은 메모리가 소모되게 된다. 또한 무한 그래프와 같이 끝이 존재하지 않을 경우 끝이 나지 않을 수 있다.

시간복잡도

void bfs(vector<vector<int>> &edge, vector<bool> &visited, int start){
    queue<int> que;
    
    visited[start] = true;
    que.push(start);
    
    int stage = 0;
    
    while(!que.empty()){
        queue<int> que2;
        
        cout << "breadth : " << ++ stage << "\n";
        
        while(!que.empty()){
            int current = que.front();
            que.pop();
            
            cout << current << "\n";
            
            for(auto next : edge[current]){
                if(!visited[next]){
                    visited[next] = true;
                    que2.push(next);
                }
            }
        }
        que = que2;
    }
}

인접 리스트로 구현된 bfs의 코드를 보면 정점은 최대 한번 방문하며 각각의 정점에 대한 간선을 for 문으로 순회하기 때문에 시간복잡도가 O(V+E) 임을 알 수 있다.

인접 행렬의 경우에도 마찬가지로 정점은 최대 한번 순회하고 다른 정점으로 가는 간선을 확인하는 과정이 최대 V번이기 때문에 O(V^2)를 시간복잡도로 가지게 된다.

Sample

bfs 샘플 코드

참고