BFS/DFS(1)
그럼 이제 본격적으로 DFS에 대해 알아보자.
DFS가 '깊이우선탐색'이라는 것은 귀에 딱지가 앉을 정도 많이 들어서 이미 알고있었다.
하지만 구체적으로 어떻게 작동하는 것일까?
이번 포스팅에서는 DFS의 작동 원리에 대해서 알아보자.
DFS는 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.
DFS는 '스택' 자료구조를 사용하며, 구체적인 동작 과정은 다음과 같다.
1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2. '스택의 최상단 노드'에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고, 방문처리를 한다.
방문하지 않은 인접노드가 없다면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 끝날때까지 반복한다.
그래프 그림을 그리면서 좀 더 자세하게 알아보자.
다음과 같은 그래프가 있다.
이 그래프를 DFS를 이용하여 탐색을 진행해보자.
시작 노드를 기준으로 가장 깊숙이 위치하는 노드에 닿을때까지 탐색하면 된다.
STEP1. 시작 노드인 1을 스택에 삽입하고 방문 처리 하기.
STEP2. 스택의 최상단 노드인 1에 방문하지 않은 노드 2, 3, 8이 있다.
DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 관행적으로 번호가 낮은 순으로 처리한다.
그렇기 때문에 이 중에서 가장 작은 노드인 2를 스택에 넣고 방문 처리 한다.
STEP3. 스택의 최상단 노드인 2에 방문하지 않은 인접 노드 7이 있다. 따라서 7번 노드를 스택에 넣고 방문 처리를 한다.
STEP4. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드 6과 8이 있다.이 중에서 가장 작은 노드인 6을 스택에 넣고 방문 처리를 한다.
STEP5. 스택의 최상단 노드인 6에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 6번 노드를 꺼낸다.
STEP6. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드 8이 있다. 따라서 8번 노드를 스택에 넣고 방문 처리를 한다.
STEP7. 스택의 최상단 노드인 8에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 8번 노드를 꺼낸다.
STEP8. 스택의 최상단 노드인 7에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 7번 노드를 꺼낸다.
STEP9. 스택의 최상단 노드인 2에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 2번 노드를 꺼낸다.
STEP10. 스택의 최상단 노드인 1에 방문하지 않은 인접 노드 3을 스택에 넣고 방문 처리한다.
STEP11. 스택의 최상단 노드인 3에 방문하지 않은 인접 노드 4, 5가 있다. 이 중에서 가장 작은 노드인 4를 스택에 넣고 방문 처리를 한다.
STEP12. 스택의 최상단 노드인 4에 방문하지 않은 인접 노드 5가 있다. 따라서 5번 노드를 스택에 넣고 방문 처리를 한다.
STEP13. 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 다음과 같다.
1 >> 2 >> 7 >> 6 >> 8 >> 3 >> 4 >> 5
DFS는 스택을 이용하는 알고리즘이기 때문에 재귀함수를 이용했을 때 매우 간결하게 구현 할 수 있다.
다음엔 DFS 문제를 풀어보면서 감을 잡아보자.
오늘 하루도 쌓였다!
이 게시글을 나동빈님의 '이것이 코딩테스트다'를 참고하여 작성되었음을 알려드립니다.