DFS, BFS

2019-07-23

DFS

어떻게 설명해야할까? 흐음.

DFS란 Depth First Search의 약자로 깊이 우선 탐색이라고 불린다. 더 깊은 것을 우선적으로 탐색하는 알고리즘이다. 맹목적으로 각 노드를 탐색할 때 사용한다. 그림을 그려 설명을 하고 싶지만 귀찮으므로 글로 설명해보려고 한다.

깊이 3개의 2진 트리가 있고 그 안에 1부터 7까지 숫자가 있다고 생각해보자.

1,2,3은 서로 연결이 되어있고 2는 4,5와, 3은 6,7과 연결이 되어있다. 맨 처음 노드의 시작은 1이며 1부터 깊이 우선 탐색을 했을때 

1->2->3->6->7->4->5 순서로 진행이 된다. 깊이를 따졌을때 1에서 2,3은 같은 깊이에 있다. 이를 순서대로 스택에 쌓고(쌓는다는것은 결국 방문했다는 의미이다) 3에 도착한 이후 다시 깊이 탐색을 하면 6,7이 같은 깊이에 있다. 둘 또한 순서대로 스택에 쌓는다. 그 이후 6과 7에 더 이상 내려갈 수 있는 노드가 없으므로 스택에 쌓여진 7을 빼고나서 6을 뺀다. 그 이후 3을 빼고 2로 왔을때 4와 5가 연결되어있고 스택에 쌓인적이 없으며 같은 깊이를 갖고 있기 때문에 4,5를 스택에 넣고 찾아본 뒤 없으므로 다시 5->4->2->1 순서로 스택에서 빼내게 된다.

스택에 들어간 순서는 위에서 말했다시피 1->2->3->6->7->4->5 이므로 이 순서대로 방문을 했다고 볼 수 있다.

(시간이 생기면 그림을 추가하여 설명할 게획이다)

 

 그림을 찾았기 때문에 다시 설명을 해보도록 하겠다(면접에서 설명하다 까여서 다시 복습할겸, 2019-10-16)

 

 위는 DFS와 BFS에 대한 그림이다. 

 DFS란 Depth First Search의 약자로 깊이 우선 탐색이라고 불린다. 위에 그림을 보면 말그대로 깊이를 우선적으로 파고들어 탐색한다. 경험상 보통 모든 노드를 방문해서 답을 찾을때 사용했다. 예를 들어 A에서 B를 갈때 갈 수 있는 방법의 수를 구할때 DFS를 사용해서 답을 구한다.

 

 BFS란 Breadth First Search의 약자로 너비 우선 탐색이라고 불린다. 본인 노드를 중심으로 연결되어있는 노드들을 탐색하고 그 뒤 그 연결된 노드들에 연결된 노드들을 탐색한다. 보통 최소 값을 구할 때 사용했던 것 같다. A에서 B를 갈때 몇번만에 최소로 갈 수 있을지 구할때 사용한다. 그이유로는 BFS는 큐를 사용하기 때문이다. 중심 노드의 주변 노드들을 큐에 저장해서 탐색하고 그 노드들의 주변 노드를 또 큐에 미리 저장해서 쌓아둔다(큐의 특성) 그렇게 쭉 계산하다가 답을 찾았을때 그만두면 그게 바로 최소값을 찾는 방법이다.

 

 설명이 뭔가 위에서 했던 말, 정의 그대로 쓴거 같은데 이게 끝이다.