기술면접 알고리즘 [Graph] : BFS (넓이 우선 탐색)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다. 

문제 링크는 제목에 링크로 걸어두었습니다.

---

BFS (Breadth First Search)

BFS 는 넓이 우선탐색으로, 큐(Queue) 자료구조 형을 사용하여 방문 체크를 진행한다. 구체적인 코드는 다음과 같다.

#include <iostream>
#include <list>
#include <queue>

using namespace std;

class Graph {
  
 int N;
 list<int>* g;
  
public:
  
  Graph(int n) : N(n) {
      g = new list<int>[n];
  }
  
  void addEdge(int i, int j) {
      g[i].push_back(j);
      //g[j].push_back(i);
  }
  
  void BFS(int s);
  
  ~Graph() { delete g; }
};

void Graph::BFS(int s) {
    queue<int> q;
    bool visit[N];
    for (auto b : visit) b = false;
    
    q.push(s);
    
    int cur;
    
    while (!q.empty()) {
        
        cur = q.front();
        visit[cur] = true;
        q.pop();
        
        cout << cur;
        for (int next : g[cur]) {
            if (!visit[next]) {
                q.push(next);
            }
        }
    }
    cout << endl;
}

int main() {
     // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    cout << "Following is Breadth First Traversal "
         << "(starting from vertex 2) \n";
    g.BFS(2);

    return 0;
}