[Algorithm] DFS, 깊이 우선 탐색

DFS, 깊이 우선 탐색

* 그래프 탐색

하나의 정점으로부터 시작하여 모든 정점들을 한 번씩 차례대로 방문하는 것이다.

 

* 깊이 우선 탐색

임의의 루트 노드부터 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

BFS 보다는 검색 속도가 느리다.

인접한 간선이 없을 경우 이전으로 돌아가야 하므로 한 번 방문한 노드는 방문했다는 것을 반드시 표시해두어야 한다.

이를 위해서는 거쳐온 정점들을 모두 저장해 두어야 하는데, 이는 재귀 호출을 이용하여 구현할 수 있다.

 

1) 임의의 한 노드와 인접해 있는 모든 노드를 탐색하고, 방문한 노드를 표시한다.

2) 임의의 노드에 더 이상 인접한 노드가 없다면 다른 노드에서 가장 가까운 갈림길로 돌아가(백트래킹) 다시 탐색을 진행한다.

3) 방문하지 않은 노드가 없는 경우 탐색을 종료한다.

 

* 적용 예시

• 깊게 탐색을 진행하고 싶을 때
• 모든 노드를 방문하고 싶을 때

 

* 깊이 우선 탐색 과정

 

* 코드 구현

일반적으로 순환 호출을 사용하여 구현한다.

void search(Node root) {
  if (root == null) return;
  // 1. root 노드 방문
  visit(root);
  root.visited = true; // 1-1. 방문한 노드를 표시
  
  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 3. 방문하지 않은 정점을 찾는다.
      search(n); // 4. root 노드와 인접한 정점 정점을 시작 정점으로 DFS 시작
    }
  }
}

 

---

- 관련 연습 문제

www.acmicpc.net/problem/1260

programmers.co.kr/learn/courses/30/lessons/43162

 

---

[참고한 곳]

gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

manducku.tistory.com/23