[자료구조C#] 그래프 탐색 알고리즘- DFS (깊이 우선 탐색) 개론

https://nybot-house.tistory.com/113

[자료구조] 그래프 개요

이전 포스트에서 그래프의 개요에 대해 알아 보았다. 이제 실제 그래프를 구현해보고, 이 그래프를 탐색하는 방법 중 하나인 DFS(깊이 우선 탐색) 방법에 대해 알아보자.

그래프 생성

그래프를 구현해보기에 앞서서, 앞서 만들어 봤던 가상의 소셜 네트워크 관계도를 생각해보자.
이제 우리는 그녀들과 데이트를 하려고 한다. 다만 서로 관계가 있는, 즉 연결되어 있는 인물들만 만날 수 있다.
우리는 그녀들을 모두 만나기 위해 그녀들을 순회할 알고리즘을 만들어 볼 건데, 그럼 필자가 제일 좋아하는 1번 제니부터 만난다고  하면 대체 어떤 기준으로 방향을 선택해서 데이트 순회를 해야 하는 것일까? 

대체 어떤 기준으로 방향을 선택해서 각 인물 정점들을 순회해야 할까?

우선, 순회하기 전 주어진 관계도를 그래프로 표현해보면 다음과 같게 될 것이다.

0: [1, 3]
1: [0, 2, 3]
2: [1]
3: [0, 1, 4]
4: [3, 5]
5: [4]

각 인물에 0번부터 5번까지 번호를 붙였고, 연결된 관계를 정리해서 그래프로 표현해 봤다. 

그래프의 순회 기준은?

• DFS (Depth First Search) 깊이 우선 탐색
• BFS (Breadth First Search) 너비 우선 탐색
  (*BFS는 추후 다른 포스트에서 다룰 예정)

DFS (Depth First Search) 깊이 우선 탐색

 깊이 우선 탐색은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 한 정점의 분기를 최대한 깊이 탐색한 후, 더 이상 깊이 갈 수 없으면 다시 되돌아와 다른 분기를 탐색하는 방법이다. 즉, DFS는 인접한 정점 중 가장 먼저 나오는 정점으로 이동하고 그 정점의 분기를 최대한 깊이 탐색한 후에 더 이상 탐색할 곳이 없으면 다시 되돌아와 다른 분기로 탐색하는 방식이다. 
위 예시를 통해 자세히 살펴보자. 우리가 첫 번째 데이트를 시작할 인물을 1번 제니라고 한다면, 그 다음으로 제니와 연결되어 있는 0번 카리나 또는 3번 수지를 선택하여 방문 해야 하는데, DFS는인접한 정점 중 가장 먼저 나오는 정점으로 이동한다. 우리는 각 정점의 번호(임의로 붙인 번호인데, 데이터에는 당연히 순서가 있으므로 그것을 나타낸다) 를 통해  순서를 알 수 있다. 즉, 제니(1)에서 연결된 첫 번째 정점인 카리나(0)으로 이동한다. 순서를 정리해보자.

1. 제니(1)에서 시작.
2. 제니(1)에서 연결된 첫 번째 정점인 카리나(0)로 이동한다.
3. 카리나(0)에서 연결된 첫 번째 정점인 제니는 이미 방문했으므로, 두 번째 정점인 수지(3)로 이동한다.
4. 수지(3)에서 연결된 첫 번째 정점인 카리나(0)와 두 번째 정점 제니(1)는 이미 방문했으므로, 아이린(4)으로 이동.
5. 아이린(4)에서 연결된 첫 번째 정점 수지(3)는 이미 방문했으므로 두 번째 정점인 원영(5)으로 이동.
6. 원영(5)에서 연결된 유일한 정점인 아이린(4)은 이미 방문했다. 여기서 더 이상 갈 수 없으므로 이전 정점 아이린(4)으로 되돌아간다!
7. 아이린(4)으로 되돌아와서 다른 미탐색 경로를 찾으려 하지만 모든 인접 정점이 이미 방문되었다. 다시 수지(3)로 되돌아간다.
8. 수지(3)로 되돌아와서 다른 미탐색 경로를 찾으려 하지만 모든 인접 정점이 이미 방문되었으니 카리나(0)으로 되돌아간다.
9. 카리나(0)로 되돌아와서 다른 미탐색 경로 탐색 시도, 모든 인접 정점 이미 방문.제니(1)로 되돌아간다.
10. 제니(1)에서 다시 탐색을 이어가는데 연결된 두 번째 정점인 지수(2)를 방문하지 않았다! 지수(2)로 이동한다.
11. 지수(2)에서 연결된 유일한 정점인 제니(1)는 이미 방문했다. 여기서 더 이상 갈 수 없으므로 이전 정점으로 리턴.
12. 제니(1)에서 연결된 세 번째 정점인 수지(3)로 이동하는데, 수지(3)도 이미 방문했다. 더 이상 탐색할 경로가 없으므로 탐색을 종료한다.

따라서 제니(1번)부터 시작하여 DFS에 따라 탐색하는 순서는 다음과 같다.

제니(1) -> 카리나(0) -> 수지(3) -> 아이린(4) -> 원영(5) -> 지수(2)

그래프가 끊겨있을 경우

만약 관계도가 이렇게 중간에 끊겨져 있다면 어떻게 될까?

제니부터 방문한 우리는 카리나, 수지, 지수와 만날 수 있지만 아이린 에게는 영영 도달할 수가 없게 된다. 
물론 시작할 때 아이린부터 방문하게 된다면 아이린과 원영을 만날 수 있겠지만 역시 카리나, 수지, 제니, 지수와는 영영 만나지 못한다.

DFS의 특징

• 시간 복잡도: O(V+E), 여기서 V는 정점의 수, E는 간선의 수이다.
• 공간 복잡도: 재귀를 사용하면 재귀 호출로 인한 스택 공간을 사용하며, 스택을 사용하면 명시적인 스택이 필요하다.
• 원전 탐색: 모든 경로를 탐색하여 목적지에 도달할 수 있는지 여부를 결정할 수 있다.
• 경로 발견: 특점 정점에서 다른 정점으로의 경로를 찾는 데 유용하다.

DFS의 응용

• 미로 찾기: 미로에서 출구를 찾는 문제
• 사이클 검출: 그래프에서 사이클이 존재하는지 여부 확인
• 강한 연결 요소(SCC): 방향 그래프에서 강한 연결 요소를 찾는 알고리즘의 기초
• 위상 정렬: 방향 그래프에서의 위상 정렬