Algorithm&DataStructure - DFS

Algorithm&DataStructure - DFS

1 DFS

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

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

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

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

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

2 백준 2606번: 바이러스

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

*재귀를 활용한 dfs

#include #include #include class Graph{ private: int numOfNodes; int numOfPaths; const static int MAXNODES = 100; std::set relations[MAXNODES]; public: Graph(int numOfNodes, int numOfPaths):numOfNodes(numOfNodes), numOfPaths(numOfPaths){ for(int i =0; i visited(numOfNodes,false); int numOfInfectedPC = 0; dfs(0,numOfInfectedPC,visited); return numOfInfectedPC; } void dfs(int startNode,int& numOfInfectedPC, std::vector& 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를 그린다.

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

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

*stack을 활용한 dfs

#include #include #include #include class Graph{ private: int numOfNodes; int numOfPaths; const static int MAXNODES = 100; std::set relations[MAXNODES]; public: Graph(int numOfNodes, int numOfPaths):numOfNodes(numOfNodes), numOfPaths(numOfPaths){ for(int i =0; i visited(numOfNodes,false); std::stack 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<

from http://jsdysw.tistory.com/119 by ccl(A) rewrite - 2021-08-02 18:26:09