알고리즘_개념 및 문제풀이

BFS 기본 개념 및 구현 코드

swdream 2019. 5. 1. 21:35
반응형

Source: https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

자, 이것이 BFS다. 한글로는 너비 우선 탐색이라고 한다. 그림은 쉽다. 

움직이는 그림에서 보면 제일 위에 있는 Node부터 탐색을 시작해서, 제일 위의 노드와 직접 연결된 두 번째 노드 (3개)를 탐색하고, 아래도 이와 같은 방식으로 탐색하는 것이다. 이 탐색을 하는 것이 마치 넓게 인접 노드부터 차례로 탐색하는 모양새므로 너비를 우선으로 탐색한다 -> BFS, '너비 우선'탐색이라 하는것이다. 

저 구슬 알갱이들을 node라 부르고, 그 Node들은 간선(Edge)로 이어져있다. '그래프'(Graph) 자료구조를 이용하여 구현해야하는 알고리즘이니 BFS를 보기 전에 그래프라는 자료구조 개념을 먼저 알고 오는 것이 좋다.

자, 각설하고 구현을 해보자. 그림은 단순하지만 구현은 노드를 바로 탐색(or 방문)하지 않고, 방문할 후보 노드들은 먼저 자료구조형인 한 층 한 층 queue에 담아놓고, queue에서 꺼내면서 비로소 탐색(or 방문) 한다. 

  1. 탐색을 시작할 루트 노드를 설정
  2. 루트 노드에서 간선으로 연결되어있는 다음 레벨까지의 노드들(직전 시작 노드(루트 노드)와 직접 연결된 노드들만)을 먼저 Queue에 담는다. 
  3. 먼저 1차적으로 Queue에 담은 후보 Node들을 차례로 꺼내면서 비로소 Queue에 있는 노드들을 하나씩 방문 체크한다. 
  4. Queue에 있는 노드들을 방문 체크 하면서 방문 체크한 노드의 아래 인접 노드를 또 방문 후보 노드 Queue에 넣는다.
  5. 1~4를 Queue에 남아있는 방문 후보 노드들이 없어질 때까지 반복하다보면, BFS 완료

Code는 BFS로 탐색을 할 때 우리가 탐색을 하는 노드의 순서 벡터를 반환하는 함수이다. 

#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> adj; // Adjacency List
vector<bool> discovered; // For Checking if visited the Node

vector<int> bfs(int start){
    discovered = vector<bool>(adj.size(), false); // 아직 발견한 노드는 없으므로 False로 초기화
    queue<int> q; // BFS 구현을 위해 방문 후보 노드들을 넣어둘 q를 만듭니다.
    vector<int> order;
    q.push(start); // q에 start를 먼저 넣고
    discovered[start] = true; // 처음 start 노드는 발견한 것으로 생각할 것
    
    //큐가 완전히 빌 때 까지 BFS 탐색을 시작한다.
    while(!q.empty()){
        int here = q.front(); // q에서 꺼낸 노드를 우리가 탐색을 시작하려는 노드이니 here
        q.pop(); // q의 바로 앞의 노드를 here에 담은 뒤 q 에서 날려준다.
        order.push_back(here); // 탐색 순서 벡터에 우리가 노드를 탐색하는대로 넣어준다.
        for(int i = 0; i < adj[here].size(); i++){ // 각 인접 리스트의 [here][i]를 돌며 체크
            int there = adj[here][i]; //이때 there은 here노드로부터 인접한 노드를 의미
            if(!discovered[there]){ // 이 there 가 방문을 하지 않은 노드이면 큐에 넣어줌
                q.push(there);
                discovered[there] = true; // 아울러 Discovered 벡터에도 true check
            }
        }
    }
    return order; // BFS로 탐색한 노드의 순서를 출력해준다.
}

+ 사실 DFS / BFS 의 기본 개념 자체는 이해가지만, 코드가 처음에는 익숙하지 않다.. 나는 한동안 이해가 안가고, 코드를 그대로 따라서 옮겨적고 반복해서 보고 시간이 지나서 또 다시 보고 하니 이해가 조금씩 가는데, 계속해서 보고 있으면 이해가 될 것이다. 

모르면 외워놓고 이해하자.. 

반응형