[알고리즘] C++ 로 구현한 DFS 알고리즘

코테에 자주 등장하는 DFS / BFS  중 DFS 에 대해 다뤄보려고 한다.

 

그래프와 트리를 검색하는 알고리즘 중 하나인 DFS

: 깊이 우선 탐색

 

 

 

구현시 " 스택 " 을 이용하여 구현한다.

 

---

                                          예제                                          

 

아래와 같은 그래프가 있다고 하자.

 

준비물은

• mem 스택 : 선택된 노드와 인접한 노드들을 스택에 쌓아놓고 하나씩 빼면서 살펴볼때 이용한다.
• visited 배열 : 노드가 mem 스택에 들어간 경우 값을 true 로 바꾸어 , 방문한 노드를 다시 방문하는 경우가 없도록 한다.

 

1. 제일먼저 가장 처음 노드를 스택에 넣고 , 해당 노드의 visited 를 true 로 바꾼다.

 

 

1. 스택에서 "0" 을 꺼낸다 

2. "0" 과 인접한 노드 1, 2 를 순서대로 스택에 넣는다.

3. "1" 과 "2" 에 해당하는 visited 를 true 로 바꾼다.

 

 

1. 인접한 노드를 모두 스택에 넣으면 꺼내져있던 "0" 을 출력한다.

 

 

1. 스택에서 노드 하나를 꺼낸다 . "2" 가 꺼내진다.

2. "2" 와 인접한 노드를 스택에 추가하는데 , 이때 인접한노드 "0" 과 "1" 은 이미 visited = true 이므로 스택에 추가하지않는다.

 

 

1. "2"를 출력한다.

2. 1을 스택에서 꺼낸다.

3. 꺼낸 "1" 과 인접한 노드 "3", "4" 를 차례대로 스택에 넣는다.

4. "3" 과 "4" 에 해당하는 visited = true 로 바꾼다.

 

 

1. 꺼낸 "1" 을 출력한다.

 

 

1. 스택에서 "4" 를 꺼낸다.

2. "4" 와 인접한 "1"과 "3" 은 이미 방문했으므로 따로 스택에 추가할 노드는 없다.

 

 

1. 꺼내져있던 "4" 를 출력한다.

 

 

1. 스택에서 "3" 을 꺼낸다.

2. "3" 과 인접한 노드 "1","4" 는 이미 visited = true 이므로 따로 스택에 추가하지않는다.

 

 

1. 꺼내져있던 "3" 을 출력한다.

2. mem 스택이 비었으므로 종료한다.

---

                                        C++을 이용한 구현                                       

 

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

using namespace std;

int V_size=5; // 노드의 갯수 

vector< vector<int> > adjacent={ 
		{0,1,1,0,0},
		{1,0,1,1,0},
		{1,1,0,0,0},
		{0,1,0,0,0},
		{0,0,0,0,0},
}; //인접 행렬의 표현
vector<bool> visited(V_size, false); // 방문헀으면 true, 안했으면 false
stack<int> mem; // 사용할 스택

void dfs(int start) {
	int current = start; // 제일 처음 루트 노드
	mem.push(current); // 스택에 넣고 
	visited[current] = true; // 방문표시 
	while (mem.size()!=0) {
		current = mem.top(); // 스택에서 데이터 하나 꺼내오고
		mem.pop();
		cout << "VISIT : " << current<< '\n';
		for (int i = 0; i < V_size; i++) {
			if (adjacent[current][i] != 0 && !visited[i]) { // current 와 인접한 노드들 중 방문을 아직 안했고 0 도아니면
				current = i;
				mem.push(current); // 스택에 집어넣고
				visited[current] = true; // 방문을 true 로 바꾼다
			}
		}
	}
}

void dfsAll() { //그래프가 분리되어있을 수 있으니까 모든 그래프를 다 둘러봐야해서 !
	visited = vector<bool>(adjacent.size(), false);
	for (int i = 0; i < adjacent.size(); i++) {
		if (!visited[i]) dfs(i); // 방문하지 않았으면 dfs 실행
	}
}


void main() {
	dfsAll();
}

 

장점

1. 저장공간의 수요가 비교적 적다

2. 목표노드가 깊은 단계에 있는경우 해를 빠르게 구할 수 있다.

 

단점

1. 해가 없는 경로에 깊이 빠질 수 있다.

2. 얻어진 해가 최단 경로는 아닐 수 있다.