DFS ( Depth First Search )

 

DFS 란 단어 뜻 그대로 깊이 우선 탐색이라는 뜻이다.

 

 

 

그래서 구현은?

 

우선 DFS는 두 가지 정보를 우리가 알아야한다.

 

위의 그림에서 D를 방문하고 H를 방문했다고 하자.

다음에는 어디로 가야 할까?

 

우리는 당연히 안다.

다시 3번으로 올라왔다가 5번으로 가야 되는걸.   이걸 코드로 실행하려면 다음의 두 정보가 필요하다.

 

① 전에 방문한 정점(vertex)을 알아야 한다. 따라서 각 정점(vertex)의 방문 여부를 저장하는 자료구조가 필요핟.

- 한번 방문한 정점(vertex)이라면 들릴 필요가 없다.

 

② 더이상 방문 할 정점이 없으면 이전의 정점으로 돌아가야 합니다. ( 이전 정점의 정보를 알고 있어야 한다. )

- 위 DFS 예시에서 나오는거 처럼 H 의 자식노드가 없어 더이상 갈곳이 없다면 그 전 노드로 돌아가 방문하지 않은 i 노드를 방문해야한다.

 

 

이 두 가지를 충족시키는 방법은  Stack 자료구조를 사용하거나 재귀함수 를 이용하는 것이다.

 

---

참고로 그래프를 코드로 표현하는 방법에는 두 가지가 있다.

 

< 1. Adjacency Matrix>

1. 그래프의 정점(vertex)들을 행렬(Matrix)로 표시해서 인접하면 1, 아니면 0으로 표시하여 2차원 행렬로 표현.

 

< 2. Adjacency list>

2. 배열에 정점(vertex)들을 나열하고 각 배열에 저장되어 있는 정점(vertex) 옆으로 리스트 형식으로 서로 인접한 정점들을 표시( 순서 상관 X ) - 간혹 문제에 크기(숫자)가 작은 정점부터 방문하라고 한다면 Sort 해주면 된다.

---

[ Recursion 이용한 DFS 구현 ]

#include<iostream>
#include<vector>

using std::endl;
using std::cout;

const int adjacent2_size=7;  // 주어진 그래프의 vertex 개수
std::vector<std::vector<int>> adjacent = { 7 ,std::vector<int>(7,0)} ;  // 인접행렬의 표현 (V x V) 행렬
std::vector<bool> visited(adjacent2_size, false);
// 0 번 인덱스도 사용.

//  ==========================================================
//  < 1. Adjacency Matrix > 로 그래프를 표현했을때 DFS 
void DFS(int here) {     

	cout << "visit " << here << '\n';
	visited[here] = true;

	for (int i = 0; i < adjacent2_size; i++) {
		if (adjacent[here][i] != 0 && !visited[i]) {

			DFS(i);
		}
	}
}

//  ==========================================================
//   < 2. Adjacency list > 로 그래프를 표현했을때 DFS 

// 0 index는 안쓰고 1번 부터 쓸거기 때문에 +1 할당할때 +1을 하여 할당해준다.
std::vector<std::vector<int>> adjacent2(9); // 행이 9행인 2차원 vector 생성 / 열은 가변적.
std::vector<bool> visited2(adjacent2.size(), false);


void DFS2(int here) {

	visited2[here] = true;
	cout << "visit2 : " << here << '\n';

	for (int i = 0; i < adjacent2[here].size(); i++) {
		int next = adjacent2[here][i];
		if (!visited2[next]) {
			DFS2(next);
		}
	}
}

 

여기서 주의할 점은

 

한번의 DFS로 모든 노드가 순회 된다는 보장은 없기 때문에 

모든 노드를 방문하여야 된다면, DFS를 한번 돌고 방문하지 않은 노드를 찾아서 DFS를 다시 실행 시켜줘야 된다.

 

for (int i = 0; i < n; i++) {
		if (visited[i] == false) {
            //  인접 행렬로 표현했을때 행에서 1이 1개라면 자기 자신 말고는 인접한 노드가 없는 것이다.
			if (std::count(adjacent[i].begin(), adjacent[i].end(), 1) > 1) {  	
				Dfs(i);
			}
		}
	}

---

[ Stack을 이용한 DFS 구현 ]

( 작은 노드 부터 실행하기 위해 sort 를 해주었다. )

std::vector<int> adj_list[10];
bool visited[10] = { false, };
std::stack<int> st;

// 인접 리스트로 구하기.
void DFS(int start) {
	st.push(start);
	visited[start] = true;
	std::cout << start << " ";

	while (!st.empty()) {
		int cur = st.top();

		st.pop();

		std::sort(adj_list[cur].begin(), adj_list[cur].end());

		for (size_t i = 0; i<adj_list[cur].size(); i++) {

			int next = adj_list[cur][i];

			if (!visited[next]) {
				st.push(cur);  < 위에서 pop()을 해줬기 때문에 cur를 다시 push 해준다.
				st.push(next);
				std::cout << next << " ";
				visited[next] = true;
				break;
			}
		}
	}
}

 

주의 해야 할점은

st.push(cur);  //  위에서 pop()을 해줬기 때문에 cur를 다시 push 해준다.
st.push(next);

 

push를 두번 해준다는 점이다.

이것이 스택을 사용하는 이유이다.

 

DFS에서 스택을 사용 하는 명확한 이유는

 

어떠한 노드 에서 더 이상 인접한 노드가 없거나 전부 방문한 노드들 일때 그 이전 노드로 돌아가 이전 노드의 다른 인접한 노드를 방문해야하고 스택은 그것을 가능하게 하는 자료구조 이기 때문이다.

 

스택에는 당연히 그 이전 노드를 가지고 있어야한다.

 

위와 같이 push를 두번 해주지 않고, 한번 해주게 되면 이전 노드의 값이 스택에 없어지게되고 인접한 노드가 없거나 방문한 노드만 있을때 뒤로 가는 제 기능을 발휘하지 못하게된다.

 

가끔 DFS 코드를 구글링 해보다 보면 next 만 push 해주는 코드를 볼 수 있는데 인접한 노드가 2개 이상인 그래프를 만나면 오류가 나는것을 확인 할 수 있을것이다. ( 모든 노드가 인접한 노드를 1개씩만 가지고 있다면 상관없다. )

 

다시 돌아와서 무튼 이러한 이유로 push 두번 해주어야한다.

---

 

근데 나는 위 코드가 뭔가 별로였다.

 

왜 헷갈리게 스택에서 뺐다가 넣었다가 하는지...

 

다른 방법이 있는지 골머리 굴려보다가 안되서 포기하고 구글 검색을 하던 도중에 내가 정확히 찾던 코드 발견!!

 

 

void DFS(int start) {
	st.push(start);
	visited[start] = true;
	std::cout << start << " ";

	while (!st.empty()) {
		int cur = st.top();

		std::sort(adj_list[cur].begin(), adj_list[cur].end());

		size_t i;    //  for 문 밖에서다가 선언.
		for (i = 0; i<adj_list[cur].size(); i++) {

			int next = adj_list[cur][i];

			if (!visited[next]) {
				st.push(next);
				std::cout << next << " ";
				visited[next] = true;
				break;
			}
		}
		if (i == adj_list[cur].size()) {  // 연결된 노드가 없거나 모두 방문한 경우
			st.pop();
		}
	}
}

 

if (i == adj_list[cur].size()) {  // 연결된 노드가 없거나 모두 방문한 경우
			st.pop();
	}

 

i == adj_list[cur].size() <== adj_list[cur].size() 가 만약 0 이라면 for문 에서 i가 0이 되고 바로 빠져 나오니깐 둘의 값은 같고.

i 의 인접한 노드 전부를 이미 방문한 경우 for 문에서 i가 adj_list[cur].size()랑 같아져서 나오기 때문에

 

결과적으로는 둘의 값이 같으면 연결된 노드가 없거나 모두 방문한 경우가 된다