Algorithm&DataStructure - DFS

1 DFS

- 깊이 우선 탐색, Depth-First Search

- 그래프를 순회(하나의 정점에서 시작해서 차례대로 모든 정점들을 한 번씩 방문) 하는 알고리즘 중 하나

- 비유를 하자면 미로에서 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 진행할 수 없을 때, 가장 가까운 분기점으로 되돌아와 다른 방향으로 다시 탐색을 진행. 모든 노드를 순회할때까지 이 과정을 계속함

- 탐색 시 어떤 노드에 대해서 방문을 했는지 안 했는지를 알고 있어야 한다.

- 스택을 활용한 구현, 재귀 호출을 활용한 구현 2가지가 존재, 본질적으로 스택 구조를 활용한다는 점에서는 같은 방식임.

2 백준 2606번: 바이러스

- 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

*재귀를 활용한 dfs

#include <iostream>
#include <set>
#include <vector>

class Graph{
private:
  int numOfNodes;
  int numOfPaths;
  const static int MAXNODES = 100;
  std::set<int> relations[MAXNODES];
public:
  Graph(int numOfNodes, int numOfPaths):numOfNodes(numOfNodes), numOfPaths(numOfPaths){
    for(int i =0; i<numOfPaths; i++){
      int a,b;
      scanf("%d %d",&a,&b);
      relations[a-1].insert(b-1);
      relations[b-1].insert(a-1);
    }
  }
  
  int CountInfectedPC(){
    std::vector<bool> visited(numOfNodes,false);
    int numOfInfectedPC = 0;
    dfs(0,numOfInfectedPC,visited);
    return numOfInfectedPC;
  }

  void dfs(int startNode,int& numOfInfectedPC, std::vector<bool>& visited){
    visited[startNode] = true;
    numOfInfectedPC++;

    for(const auto elem:relations[startNode]){
      if(!visited[elem]){
        dfs(elem,numOfInfectedPC,visited);
      }  
    }
  }
};

int main(){
  int numOfNodes, numOfPaths;
  std::cin>>numOfNodes>>numOfPaths;

  Graph graph(numOfNodes, numOfPaths);
  std::cout<<graph.CountInfectedPC()-1;
}

- 노드의 수와 노드간의 연결관계를 바탕으로 graph를 그린다.

- 그린 그래프를 dfs방식으로 순회하는데 각 노드들에 대한 방문 여부를 알고 있어야한다.

- 모든 노드를 방문할 때 까지 탐색이 반복되는데 시작 노드로부터 나아갈 길이 없을 때까지 깊이 우선으로 방문을 시도한다.

*stack을 활용한 dfs

#include <iostream>
#include <set>
#include <vector>
#include <stack>

class Graph{
private:
  int numOfNodes;
  int numOfPaths;
  const static int MAXNODES = 100;
  std::set<int> relations[MAXNODES];
public:
  Graph(int numOfNodes, int numOfPaths):numOfNodes(numOfNodes), numOfPaths(numOfPaths){
    for(int i =0; i<numOfPaths; i++){
      int a,b;
      scanf("%d %d",&a,&b);
      relations[a-1].insert(b-1);
      relations[b-1].insert(a-1);
    }
  }
  
  int CountInfectedPC(){
    int numOfInfectedPC = 0;
    dfs(0,numOfInfectedPC);
    return numOfInfectedPC;
  }

  void dfs(int startNode,int& numOfInfectedPC){
    std::vector<bool> visited(numOfNodes,false);
    std::stack<int> stack;

    stack.push(startNode);
    visited[startNode] = true;
    numOfInfectedPC++;

    while(!stack.empty()){
      int before = stack.top();
      for(const auto elem:relations[stack.top()]){
        if(!visited[elem]){
          stack.push(elem);
          visited[elem] = true;
          numOfInfectedPC++;   
          break;
        }
      }
      if(before == stack.top()){
        stack.pop();
      }
    }
  }
};

int main(){
  int numOfNodes, numOfPaths;
  std::cin>>numOfNodes>>numOfPaths;

  Graph graph(numOfNodes, numOfPaths);
  std::cout<<graph.CountInfectedPC()-1;
}