자료구조 - 그래프 탐색 DFS 그림으로 쉽게 이해하기

자료구조 - 그래프 탐색 DFS 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로

자료구조 - 그래프 탐색 DFS 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.

그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

바로 시작하겠습니다.

 

 

 

 

 

- 그래프 탐색 DFS

이번 포스팅에서는 그래프의 탐색 방법 중 하나인 DFS에 대해서 알아보겠습니다.
DFS는 Depth-First Search의 약자로 한글로 번역하면 깊이우선탐색 이라고 합니다. BFS가 가까운 곳부터 탐색하는 방법 이라면 DFS는 갈 수 있는 최대한 멀리까지 탐색하는 방법이라고 생각하시면 될 것 같습니다. 우리가 배웠던 트리탐색에서 전위탑색(preorder), 중위탐색(inorder), 후위탐색(postorder)이 바로 DFS의 일종입니다. 트리를 이 3가지 방법 중 어느것으로 탐색을 하더라도 왼쪽 노드를 방문하는 순간 왼쪽 노드에 서브트리가 있다면 자식노드가 없을 때까지 계속해서 왼쪽 서브트리를 타고 들어가서 방문을 합니다. 마찬가지로 오른쪽 서브트리를 방문 할 때도 오른쪽 자식노드가 더 이상 자식이 없을 때까지 끝까지 타고 들어가서 방문을 합니다. 이렇게 갈 수 있는 최대한 멀리가지 가서 탐색하는 방법이 바로 깊이 우선 탐색, DFS입니다.

 

 

- DFS의 특징

BFS는 큐를 이용해서 구현했다면 DFS는 스택을 이용해서 구현한다는 특징이 있습니다.
물론 DFS는 스택으로 구현하는 방법도 있고 재귀호출로 구현할 수 있는 방법도 있습니다. 다만 재귀호출 자체가 함수의 콜스택이 쌓이는 동작이기 때문에 코드상에서 우리가 명시적으로 선언한 스택은 없지만 내부적으로 함수호출 자체가 스택처럼 동작을 하게 됩니다. 그래서 결론적으로 BFS는 큐, DFS는 스택기반의 구현이라는 것을 기억하시면 되겠습니다.

 

 

그래프 DFS 예제

 

 

- DFS의 노드 방문 순서

위 그래프 예시는 BFS에서도 예시로 들었던 그래프인데요, BFS와 비교하여 DFS에서는 같은 그래프를 어떤 순서로 방문하게 되는지 같이 한 번 알아보겠습니다. 우선 시작점은 A노드로 시작합니다. 그러면 스택에 A노드가 먼저 들어오게 되겠죠.

 

 

스택에 A노드가 들어온 모습

 

 

그러면 이제부터 스택에 있는 데이터를 하나씩 가져오면서 연결된 vertex들을 스택에 넣어주는 작업을 할 것입니다. 먼저 스택에 쌓여있는 A를 꺼내오면서 A노드를 방문하게 되고, 그와 연결된 B노드를 스택에 삽입을 하게 되겠죠. 그러면 현재까지 A만 방문했고, 스택에는 B가 남아 있는 상태입니다.

 

 

A를 방문하고 연결된 B 삽입

 

 

그 다음으로 스택에서 B를 가져오면서 B를 방문하고, B와 연결된 노드인 C, D, E를 스택에 삽입해줍니다. 여기까지는 BFS와 큰 차이가 없어 보입니다. 그러면 현재까지 A - B 순서로 방문했고, 스택에는 C와 D와 E가 남아 있는 상태입니다.

 

 

C,D,E가 삽입된 모습

 

 

여기까진 BFS와 크게 다를 것이 없어보이지만 BFS와 다른점이 이제부터 나타납니다. BFS가 사용하는 큐는 First In First Out의 자료구조였다면, DFS가 사용하는 스택은 First In Last Out의 자료구조입니다. 그렇기 때문에 이번엔 제일 마지막에 삽입된 E를 꺼내오면서 E를 방문하게 되고, E와 연결된 노드들을 삽입하게 됩니다. 어떤 노드들이 연결되어 있나 보니 B와 D가 연결되어 있습니다. 그런데 이 두 노드는 모두 이미 삽입이 된 상태이므로 아무것도 삽입되지 못하고 턴이 종료가 되게 됩니다. 그러면 현재까지 A - B - E 순서로 방문했고, 스택에는 C와 D가 남아 있는 상태입니다.

 

 

C와 D가 남아있는 모습

 

 

그 다음으로 이제는 D가 스택의 탑에 있게 되죠. 그래서 D를 꺼내오면서 D를 방문하게 됩니다. 그리고 D와 연결된 노드를 삽입해줘야 하는데 이미 방문했거나 스택에 삽입된 노드들을 제외하면 스택에 들어갈 수 있는 노드는 G와 H입니다. 그래서 G와 H를 스택에 삽입을 하게 됩니다. 그러면 현재까지 A - B - E - D 순서로 방문했고, 스택에는 C, G, H가 남아 있는 상태입니다.

 

 

C, G, H가 남아있는 모습

 

 

그 다음으로 스택의 탑에 있는 H노드를 꺼내오면서 H노드를 방문하게 됩니다. 그리고 H노드와 연결된 노드 중에 스택에 들어갈 노드는 없기 때문에 그대로 턴이 종료가 됩니다. 그러면 현재까지 A - B - E - D - H순서로 방문했고, 스택에는 C, G가 남아 있는 상태입니다.

 

 

C, G 노드가 남아있는 모습

 

 

그 다음으로 G노드를 꺼내오면서 G노드를 방문하게 되고, 마찬가지로 G노드와 연결된 노드를 삽입해야하는데 아무것도 없기 때문에 턴이 종료되게 됩니다. 만약에 추가할수 있는 노드가 있다면 그 노드가 스택에 들어가고, 다음 턴에 그 노드를 방문 하게 되겠죠. 그래서 BFS처럼 가까운 곳 부터 탐색하는 것이 아니라, 일단 가능한 멀리 깊이까지 방문한 노드가 있으면 그 노드부터 방문하는 형태가 되기 때문에 깊이우선탐색이라는 이름이 붙게 된 것입니다. 그러면 현재까지 A - B - E - D - H - G 순서로 방문했고, 스택에는 C가 남아 있는 상태입니다.

 

 

C만 남아있는 모습

 

 

그 다음으로 스택에 남아있는 C노드를 가져오면서 C노드를 방문하게 되고, C노드와 연결된 노드 중에 이미 방문했던 노드들을 제외하면 F노드만 스택에 삽입을 하게 됩니다. 그러면 현재까지 A - B - E - D - H - G - C순서로 방문했고, 스택에는 F가 남아 있는 상태입니다.

 

 

C노드를 꺼내고 F노드 삽입된 모습

 

마지막으로 스택에 남아있는 F노드를 꺼내면서 F노드를 방문하게 되고 더 이상 추가할 노드가 없기 때문에 깊이우선탐색 DFS가 종료됩니다. 결과적으로 방문 순서는 A - B - E - D - H - G - C - F순서로 방문하면서 DFS가 종료된 것입니다.

 

 

 

DFS종료

 

 

- BFS와 DFS 노드방문 순서 비교

같은 그래프를 BFS와 DFS로 탐색한 방문 순서를 비교해보면 BFS는 A - B - C - D - E - F - G - H 순서로 방문했고, 같은 그래프를 DFS로 탐색하면 A - B - E - D - H - G - C - F 순서로 방문한 것을 알 수 있습니다. 사실 매커니즘은 동일했습니다. 자료구조가 빌 때까지 자료구조에서 노드를 꺼내오면서 꺼내온 노드와 연결된 노드를 자료구조에 넣는것입니다. 그런데 그 자료구조가 큐냐 스택이냐에 따라서 결과가 다르게 나오는거죠. 

 

오늘은 이렇게 자료구조 - 그래프 탐색 DFS 그림으로 쉽게 이해하기에 대해서 알아보았습니다.

다음 포스팅도 기대해주세요.

감사합니다.