DFS 알고리즘 (1) - 이론

오늘은!!

코딩테스트를 볼때 DFS/BFS를 이용해야 풀 수 있는 문제들이 자주 출제 되기 때문에, DFS / BFS 알고리즘에 관하여 정리하려고 합니다.

시작~

 

목차

1. DFS 알고리즘이란?
2. 이진 탐색을 이용한 DFS 탐색 순서 알아보기

 

 

 

 

 

1. DFS(Dept First Search) 알고리즘 이란?

Dept First Search(이하 DFS)는 깊이를 우선 탐색하는 알고리즘 이다.

주로 Stack을 이용하여 구현되며, 코딩 테스트를 이용하여 구현할때는 재귀함수를 이용하여 구현하기도 한다.

주로 2차 행렬 넓이 구하기, 완전 탐색 문제 등에 자주 이용된다.

 

 

2. DFS 탐색 순서 이진 탐색을 이용한 DFS 탐색 순서 알아보기

사진 1. 이진 트리

 

이렇게 이진트리 하나가 있다고 하자. 그럼 DFS는 어떻게 탐색을 하는가?
위의 예시로 진행!

2.1. 1부터 시작할 것이기 때문에 1을 일단 push 한다. 그리고 탐색 한 자리는 탐색했다는
      마커 표시

사진 1-1. DFS 탐색 순서(1)

 

2.2. 1을 pop 한 후 1의 자식노드가 있으면 push한다

사진 1-2 DFS 탐색 순서(2)

 

2.3. 3 pop()하면서 방문체크, 이후 3의 자식이 있으면 자식들 push

사진 1-3 DFS 탐색 순서(3)

 

2.4. 3의 자식노드인 6,7 순서대로 push

사진 1-4. DFS 탐색 순서(4)

 

2.5. 7부터 자식 없으니 pop, 6 자식 없으니 pop

사진 1-5. DFS 탐색 순서(5)

 

2.6.  2 pop 이후 자식도느 push

사진 1-6. DFS 탐색 순서(6)

 

(마지막)2.7. 2의 자식노드 push

사진 1-7. DFS 탐색 순서(7)

 

이렇게 돌아간다. DFS 탐색을 이용하여 전위식 / 중위식/ 후위식을 표현하도록 만들 수 있다.

암튼 개념은 이렇고, 코드로 구현하는건 다음 글에서 진행하겠습니다.