백준_1260_DFS와 BFS

 

 

DFS ( 깊이 우선 탐색 ) 와

BFS ( 너비 우선 탐색 ) 에 대한 문제입니다.

 

DFS는 그래프가 있을 때 인접한 vertex중 값이 작은 것부터 깊게 탐색하는 것이고,

BFS는 그래프가 있을 때 인접한 모든 vertex를 값이 작은 순으로 탐색하고 그 다음에 깊게 들어가는 방식입니다.

 

따라서,

DFS는 Stack 혹은 재귀를 사용하여 구현할 수 있고 (LIFO)

BFS는 Queue 를 사용하여 구현할 수 있습니다. (FIFO)

 

코드)

main함수입니다.

문제에 맞는 조건의 수를 입력받아 그래프를 만들고 탐색하도록 작동시킵니다.

int main(void) {
  int N, M, V;
  std::cin >> N >> M >> V;

  AdjMatGraph<int> m(N + 1);
  for (int i = 1; i <= N; i++) m.InsertVertex(i);

  int u, v;
  for (int i = 0; i < M; i++) {
    std::cin >> u >> v;
    m.InsertEdge(u, v);
  }

  // m.PrintMatrix();
  m.DFS(V);
  m.BFS(V);

  return 0;
}

 

 

그래프 클래스 코드입니다.

탐색할 배열을 만들고

DFS와 BFS, 그리고 디버깅용 PrintMatrix까지 가능하도록 만들었습니다.

#include <iostream>
#include <queue>
#include <stack>

template <typename T>
class AdjMatGraph {
 public:
  struct Vertex {
    T item = T();
  };

  AdjMatGraph(int max_vertices) {
    max_vertices_ = max_vertices;

    matrix_ = new int*[max_vertices_];
    for (int i = 0; i < max_vertices_; i++) {
      matrix_[i] = new int[max_vertices_];
      for (int j = 0; j < max_vertices_; j++) {
        matrix_[i][j] = 0;
      }
    }
    vertices_ = new Vertex[max_vertices_];
  }

  ~AdjMatGraph() {
    delete[] vertices_;

    for (int i = 0; i < max_vertices_; i++) {
      delete[] matrix_[i];
    }
    delete[] matrix_;

    if (visited_) delete[] visited_;
  }

  void PrintMatrix() {
    if (!n_) {
      std::cout << "Empty" << '\n';
      return;
    }

    for (int i = 0; i < n_; i++) {
      for (int j = 0; j < n_; j++) {
        std::cout << matrix_[i][j] << " ";
      }
      std::cout << '\n';
    }
    std::cout << '\n';
  }

  void InsertVertex(T item) {
    vertices_[n_].item = item;
    n_++;
  }

  void ResetVisited() {
    if (!visited_) visited_ = new bool[max_vertices_];

    for (int i = 0; i < max_vertices_; i++) {
      visited_[i] = false;
    }
  }

  void InsertEdge(int u, int v) {
    matrix_[u - 1][v - 1] = 1;
    matrix_[v - 1][u - 1] = 1;
  }

  void DFS(int V) {
    if (!visited_) ResetVisited();
    std::stack<int> s;
    s.push(V - 1);

    while (!s.empty()) {
      int temp = s.top();
      s.pop();

      if (!visited_[temp]) {
        std::cout << temp + 1 << " ";
        visited_[temp] = true;
      } else {
        continue;
      }

      for (int i = n_ - 1; i >= 0; i--) {
        if (matrix_[temp][i] && !visited_[i]) {
          s.push(i);
        }
      }
    }
    std::cout << '\n';
  }

  void BFS(int V) {
    ResetVisited();
    std::queue<int> q;
    q.push(V - 1);
    visited_[V - 1] = true;

    while (!q.empty()) {
      int temp = q.front();
      q.pop();
      for (int i = 0; i < n_; i++) {
        if (matrix_[temp][i] && !visited_[i]) {
          q.push(i);
          visited_[i] = true;
        }
      }
      std::cout << temp + 1 << " ";
    }
    std::cout << '\n';
  }

 private:
  int** matrix_ = nullptr;
  Vertex* vertices_ = nullptr;
  int n_ = 0;             // size
  int max_vertices_ = 0;  // capacity
  bool* visited_ = nullptr;
};

 

위 코드에서 보시다시피 DFS는 스택을 사용하여 만약 이 vertex를 방문했으면 지나치고, 방문하지 않았으면 더 깊게 들어가는 방식입니다.

 if (!visited_[temp]) {
   std::cout << temp + 1 << " ";
   visited_[temp] = true;
   } else {
    continue;
   }

방문했는지 확인하는 이 조건문이 매우 중요하다고 할 수 있습니다.

 

BFS는 Queue를 통해 하나씩 넣어주면 되므로 DFS에 비해서는 쉽다고 느껴질 수 있습니다.