(3장-1) DFS(깊이 우선탐색) 알고리즘이란?

안녕하세요. 지칸입니다.

 

오늘 설명할 알고리즘은 DFS입니다.

삼성 SW역량테스트에서 자주 사용되는 알고리즘 중 하나입니다.

(주로 2차원 좌표상에서의 문제에 사용)

 

1) DFS란?

2) 구현하기

---

1) DFS란?

이전 편에서 그래프라는 개념에 대해 공부하였습니다.

mydirectorystory.tistory.com/13

그래프 개념과 탐색방법

이 그래프를 탐색하는 방식에 따라 DFS/BFS 알고리즘이 구분되고 있습니다.

그래프 탐색은 시작점에서 모든 정점을 차례대로 방문하는 것을 말합니다.

 

DFS란 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하고 되돌아와서 다음 분기로 넘어가는 방법입니다.

아래 그림으로 간단한 예를 설명해 보겠습니다.

분기점에서는 자신 기준 왼->오 순으로 방문한다는 가정을 했습니다.

1. 시작점 정점0에서 1, 3, 6의 분기점에서 방문 가정에 따라 정점1부터 방문합니다. (0->1)
2. 정점1에서는 분기 없이 정점2으로 방문합니다. (0->1->2)
3. 정점2에서는 왔던 길 말고는 길이 없습니다. 뒤로 되돌아 갑니다. 
4. 쭉 뒤로 되돌아와 마지막 분기였던 정점0까지 되돌아온 후 다음 정점 3을 방문합니다.(0->1->2->3)
5. 정점4,5 분기점에서 방문 가정에 따라 정점4부터 방문합니다. (0->1->2->3->4)
6. 다시 마지막 분기점인 정점3으로 되돌아간 후 정점5를 방문합니다. (0->1->2->3->4->5)
7. 쭉 정점0까지 돌아온 후 정점6를 방문합니다. (0->1->2->3->4->5->6)
8. 정점6에서 방문하지 않은 정점이 없으니 직전 정점으로 되돌아갑니다.
9. 정점0에서 이제 새로 방문할 정점이 없으니 뒤로 돌아갑니다.
10. 앗? 정점0부터 시작했으니 뒤는 없네요?? 탐색을 종료합니다.

DFS 알고리즘의 동작 순서대로 글로 설명해봤습니다.

여기서 우리는 아래 본문에서 이야기한 Stack 구조가 떠오를 것입니다.

mydirectorystory.tistory.com/16

스택 이란? (STL 사용법)

3,6,8,9번의 동작을 보면 되돌아간다는 표현이 있는데 되돌아가려면 직전 방문의 위치를 알아야 합니다. 

아래 그림처럼 우리는 stack 구조를 통해 찾아갈 수 있습니다.

---

2) 구현하기

c++로 stack STL를 사용하여 구현하면 아래 코드와 같습니다.

우리가 원하는 정점 순으로 출력이 됩니다.

현재 정점과 연결된 정점을 찾는 부분이 현재는 모든 정점을 검색하는 방식으로 코딩을 했습니다.

이 부분은 문제에 따라 혹은 최적화에 따라 바뀔 수 있습니다.

(2차원 좌표를 정점으로 맵을 준다면 한 정점의 4방향으로만 간선이 연결될 수 있으니 4방향만 검색하면 됩니다.)

 

이렇게 본 글에서는 DFS 알고리즘을 공부하고 구현해 봤습니다.

앞으로 DFS 알고리즘이 적용된 문제를 풀 때는 위 코드를 템플릿으로 사용할 예정입니다.

꼭 이해했으면 좋겠습니다.